Entender cómo funcionan las funciones recursivas

Como explica el título, tengo una pregunta de programación muy fundamental que todavía no he podido asimilar. Filtrar todos los (extremadamente inteligentes) "Para comprender la recursividad, primero debe comprender la recursividad". respuestas de varios hilos en línea todavía no lo entiendo.

Entendiendo que cuando nos enfrentamos a no saber lo que no sabemos, podemos tender a hacer las preguntas equivocadas o hacer las preguntas correctas de manera incorrecta. Compartiré lo que "creo". Mi pregunta es con la esperanza de que alguien con una perspectiva similar pueda compartir algo. ¡Un poco de conocimiento que me ayudará a encender la bombilla recursiva!

Aquí está la función (la sintaxis está escrita en Swift):

func sumInts(a: Int, b: Int) -> Int {
    if (a > b) {
        return 0
    } else {
        return a + sumInts(a: a + 1, b: b)
    }
}

Usaremos 2 y 5 como nuestros argumentos:

println(sumInts(a: 2, b: 5))

Obviamente la respuesta es 14. Pero no tengo claro cómo se logra ese valor.

Estos son mis 2 problemas:

1. La función se llama de forma recursiva hasta que se cumple una condición. Esa condición es a> b. Cuando se cumple esta condición, devuelve 0. A primera vista, esperaría que el valor devuelto fuera 0, lo que obviamente es incorrecto.

2. Imprimir el valor de 'a' en cada iteración produce un valor que esperaría: 2, 3, 4, 5 (en cuyo punto 5 + 1> b que cumple la primera condición: a> b) pero todavía no ' Veamos cómo se logra el valor de 14.

Mi primer pensamiento es que algo similar a lo siguiente está sucediendo mágicamente:

var answer = a;
answer += a+1 until a > b;
return answer;   

Así que descartando la magia, simplemente no obtengo nada. Me encantaría entender lo que está sucediendo más que implícitamente.

Si alguien pudiera explicar amablemente qué sucede técnicamente durante este tipo de función y por qué el resultado no es 0 y cómo, eventualmente, a + sumInts(a: a + 1, b: b) = 14estaría para siempre en deuda con usted.

Creo que la confusión proviene de pensar en ella como "la misma función" que se llama muchas veces. Si lo considera como "muchas copias de la misma función que se llaman", entonces puede ser más claro:

Solo una copia de la función devuelve 0, y no es la primera (es la última). Entonces, el resultado de llamar al primero no es 0.

Para la segunda confusión, creo que será más fácil deletrear la recursividad en inglés. Lea esta línea:

return a + sumInts(a + 1, b: b)

como "devuelve el valor de 'a' más (el valor de retorno de otra copia de la función, que es el valor de la copia de 'a' más (el valor de retorno de otra copia de la función, que es el valor de la segunda copia de ' a 'más (... ", con cada copia de la función generando una nueva copia de sí misma con un aumento de 1, hasta que se cumpla la condición a> b.

En el momento en que alcanza la condición a> b siendo verdadera, tiene una pila larga (potencialmente arbitraria) de copias de la función en medio de la ejecución, todas esperando el resultado de la siguiente copia para averiguar qué debe agregar a 'a'.

(editar: también, algo a tener en cuenta es que la pila de copias de la función que menciono es algo real que ocupa memoria real, y bloqueará su programa si se vuelve demasiado grande. El compilador puede optimizarlo en algunos casos, pero agotar el espacio de la pila es una limitación significativa y desafortunada de las funciones recursivas en muchos idiomas)

1. La función se llama de forma recursiva hasta que se cumple una condición. Esa condición es a > b. Cuando se cumple esta condición, devuelve 0. A primera vista, esperaría que el valor devuelto fuera 0, lo que obviamente es incorrecto.

sumInts(2,5)Esto es lo que pensaría la informática si pudiera:

I want to compute sumInts(2, 5)
for this, I need to compute sumInts(3, 5)
and add 2 to the result.
  I want to compute sumInts(3, 5)
  for this, I need to compute sumInts(4, 5)
  and add 3 to the result.
    I want to compute sumInts(4, 5)
    for this, I need to compute sumInts(5, 5)
    and add 4 to the result.
      I want to compute sumInts(5, 5)
      for this, I need to compute sumInts(6, 5)
      and add 5 to the result.
        I want to compute sumInts(6, 5)
        since 6 > 5, this is zero.
      The computation yielded 0, therefore I shall return 5 = 5 + 0.
    The computation yielded 5, therefore I shall return 9 = 4 + 5.
  The computation yielded 9, therefore I shall return 12 = 3 + 9.
The computation yielded 12, therefore I shall return 14 = 2 + 12.

Como puede ver, algunas llamadas a la función en sumIntsrealidad devuelven 0, sin embargo, este no es el valor final porque la computadora aún tiene que agregar 5 a ese 0, luego 4 al resultado, luego 3, luego 2, como se describe en las últimas cuatro oraciones de los pensamientos de nuestra computadora. Tenga en cuenta que en la recursividad, la computadora no solo tiene que calcular la llamada recursiva, también tiene que recordar qué hacer con el valor devuelto por la llamada recursiva. Hay un área especial de la memoria de la computadora llamada pila donde se guarda este tipo de información, este espacio es limitado y las funciones que son demasiado recursivas pueden agotar la pila: este es el desbordamiento de pila que da su nombre a nuestro sitio web más querido.

Su declaración parece hacer la suposición implícita de que la computadora olvida dónde estaba al hacer una llamada recursiva, pero no es así, por eso su conclusión no coincide con su observación.

2.Imprimir el valor de 'a' en cada iteración produce un valor que esperaría: 2, 3, 4, 5 (en cuyo punto 5 + 1> b que cumple la primera condición: a> b) pero todavía No veo cómo se logra el valor de 14.

Esto se debe a que el valor de retorno no es en así mismo, sino la suma del valor de ay el valor devuelto por la llamada recursiva.

Para comprender la recursividad, debe pensar en el problema de una manera diferente. En lugar de una gran secuencia lógica de pasos que tiene sentido en su conjunto, usted toma un problema grande y lo divide en problemas más pequeños y los resuelve, una vez que tenga una respuesta para los subproblemas, combine los resultados de los subproblemas para hacer el solución al problema más grande. Piense en usted y sus amigos que necesitan contar la cantidad de canicas en un cubo enorme. Cada uno toma un cubo más pequeño y va a contarlos individualmente y cuando haya terminado, sume los totales. Bueno, ahora si cada uno de ustedes encuentra un amigo y divide los cubos más, entonces solo tiene que esperar a que estos otros amigos calcule sus totales, devuélvaselo a cada uno de ustedes, sume. Y así.

Debe recordar que cada vez que la función se llama a sí misma de forma recursiva, crea un nuevo contexto con un subconjunto del problema, una vez que se resuelve esa parte, se devuelve para que se pueda completar la iteración anterior.

Déjame mostrarte los pasos:

sumInts(a: 2, b: 5) will return: 2 + sumInts(a: 3, b: 5)
sumInts(a: 3, b: 5) will return: 3 + sumInts(a: 4, b: 5)
sumInts(a: 4, b: 5) will return: 4 + sumInts(a: 5, b: 5)
sumInts(a: 5, b: 5) will return: 5 + sumInts(a: 6, b: 5)
sumInts(a: 6, b: 5) will return: 0

Una vez que sumInts (a: 6, b: 5) se ha ejecutado, los resultados se pueden calcular, por lo que, al volver a subir la cadena con los resultados, obtendrá:

 sumInts(a: 6, b: 5) = 0
 sumInts(a: 5, b: 5) = 5 + 0 = 5
 sumInts(a: 4, b: 5) = 4 + 5 = 9
 sumInts(a: 3, b: 5) = 3 + 9 = 12
 sumInts(a: 2, b: 5) = 2 + 12 = 14.

Otra forma de representar la estructura de la recursividad:

 sumInts(a: 2, b: 5) = 2 + sumInts(a: 3, b: 5)
 sumInts(a: 2, b: 5) = 2 + 3 + sumInts(a: 4, b: 5)  
 sumInts(a: 2, b: 5) = 2 + 3 + 4 + sumInts(a: 5, b: 5)  
 sumInts(a: 2, b: 5) = 2 + 3 + 4 + 5 + sumInts(a: 6, b: 5)
 sumInts(a: 2, b: 5) = 2 + 3 + 4 + 5 + 0
 sumInts(a: 2, b: 5) = 14 

La recursividad es un tema complicado de entender y no creo que pueda hacerle justicia aquí. En su lugar, intentaré centrarme en la pieza de código particular que tienes aquí y trataré de describir tanto la intuición de por qué funciona la solución como la mecánica de cómo el código calcula su resultado.

El código que ha proporcionado aquí resuelve el siguiente problema: desea saber la suma de todos los números enteros desde a hasta b, inclusive. Para su ejemplo, desea la suma de los números del 2 al 5, inclusive, que es

2 + 3 + 4 + 5

Al intentar resolver un problema de forma recursiva, uno de los primeros pasos debería ser descubrir cómo dividir el problema en un problema más pequeño con la misma estructura. Así que suponga que desea sumar los números del 2 al 5, inclusive. Una forma de simplificar esto es notar que la suma anterior se puede reescribir como

2 + (3 + 4 + 5)

Aquí, (3 + 4 + 5) resulta ser la suma de todos los números enteros entre 3 y 5, inclusive. En otras palabras, si quieres saber la suma de todos los números enteros entre 2 y 5, comienza calculando la suma de todos los números enteros entre 3 y 5, luego suma 2.

Entonces, ¿cómo se calcula la suma de todos los números enteros entre 3 y 5, inclusive? Bueno, esa suma es

3 + 4 + 5

que se puede pensar en cambio como

3 + (4 + 5)

Aquí, (4 + 5) es la suma de todos los números enteros entre 4 y 5, inclusive. Entonces, si quisieras calcular la suma de todos los números entre 3 y 5, inclusive, calcularías la suma de todos los números enteros entre 4 y 5, luego sumarías 3.

¡Aquí hay un patrón! Si desea calcular la suma de los números enteros entre ayb, inclusive, puede hacer lo siguiente. Primero, calcule la suma de los números enteros entre a + 1 y b, inclusive. Luego, agregue a ese total. Notará que "calcular la suma de los números enteros entre a + 1 y b, inclusive" resulta ser más o menos el mismo tipo de problema que ya estamos tratando de resolver, pero con parámetros ligeramente diferentes. En lugar de calcular desde a hasta b, inclusive, estamos calculando desde a + 1 hasta b, inclusive. Ese es el paso recursivo: para resolver el problema más grande ("suma de a a b, inclusive"), reducimos el problema a una versión más pequeña de sí mismo ("suma de a + 1 a b, inclusive").

Si echas un vistazo al código que tienes arriba, notarás que hay este paso en él:

return a + sumInts(a + 1, b: b)

Este código es simplemente una traducción de la lógica anterior: si desea sumar de a a b, inclusive, comience sumando a + 1 a b, inclusive (esa es la llamada recursiva as sumInt), luego agreguea .

Por supuesto, este enfoque por sí solo no funcionará. Por ejemplo, ¿cómo calcularía la suma de todos los números enteros entre 5 y 5 inclusive? Bien, usando nuestra lógica actual, calcularías la suma de todos los enteros entre 6 y 5, inclusive, luego sumarías 5. Entonces, ¿cómo calculas la suma de todos los enteros entre 6 y 5, inclusive? Bueno, usando nuestra lógica actual, calcularías la suma de todos los enteros entre 7 y 5, inclusive, luego sumarías 6. Notarás un problema aquí - ¡esto sigue y sigue!

En la resolución recursiva de problemas, es necesario que haya alguna forma de dejar de simplificar el problema y, en su lugar, ir a resolverlo directamente. Por lo general, encontrará un caso simple en el que la respuesta se puede determinar de inmediato, luego estructurará su solución para resolver casos simples directamente cuando surjan. Esto se denomina típicamente un caso base o una base recursiva .

Entonces, ¿cuál es el caso base en este problema en particular? Cuando sumas números enteros de aab, inclusive, si a es mayor que b, entonces la respuesta es 0, ¡no hay números en el rango! Por lo tanto, estructuraremos nuestra solución de la siguiente manera:

1. Si a> b, entonces la respuesta es 0.
2. De lo contrario (a ≤ b), obtenga la respuesta de la siguiente manera:
   1. Calcule la suma de los números enteros entre a + 1 y b.
   2. Agregue un para obtener la respuesta.

Ahora, compare este pseudocódigo con su código real:

func sumInts(a: Int, b: Int) -> Int {
    if (a > b) {
        return 0
    } else {
        return a + sumInts(a + 1, b: b)
    }
}

Tenga en cuenta que existe casi exactamente un mapa uno a uno entre la solución descrita en pseudocódigo y este código real. El primer paso es el caso base: en el caso de que pida la suma de un rango vacío de números, obtendrá 0. De lo contrario, calcule la suma entre a + 1 yb, luego agregue a.

Hasta ahora, he dado solo una idea de alto nivel detrás del código. Pero tenías otras dos muy buenas preguntas. Primero, ¿por qué esto no siempre devuelve 0, dado que la función dice que devuelva 0 si a> b? En segundo lugar, ¿de dónde vienen realmente los 14? Veamos estos a su vez.

Probemos con un caso muy, muy simple. ¿Qué pasa si llamas sumInts(6, 5)? En este caso, rastreando el código, verá que la función simplemente devuelve 0. Eso es lo correcto, no hay números en el rango. Ahora, intente algo más difícil. ¿Qué pasa cuando llamas sumInts(5, 5)? Bueno, esto es lo que sucede:

1. Usted llama sumInts(5, 5). Caemos en elelseCaemos rama, que devuelve el valor de `a + sumInts (6, 5).
2. Para sumInts(5, 5)poder determinar qué sumInts(6, 5)es, necesitamos pausar lo que estamos haciendo y hacer una llamada sumInts(6, 5).
3. sumInts(6, 5)se llama. Entra en la ifsucursal y regresa 0. Sin embargo, esta instancia de sumIntsfue llamada por sumInts(5, 5), por lo que el valor de retorno se comunica sumInts(5, 5)a la persona que llama de nivel superior, no a ella.
4. sumInts(5, 5)ahora puede calcular 5 + sumInts(6, 5)para volver 5. Luego lo devuelve a la persona que llama de nivel superior.

Observe cómo se formó el valor 5 aquí. Comenzamos con una llamada activa a sumInts. Eso disparó otra llamada recursiva, y el valor devuelto por esa llamada le devolvió la información sumInts(5, 5). La llamada asumInts(5, 5) entonces hizo algunos cálculos y devolvió un valor a la persona que llama.

Si prueba esto con sumInts(4, 5), esto es lo que sucederá:

• sumInts(4, 5)intenta volver 4 + sumInts(5, 5). Para hacer eso, llama sumInts(5, 5).
  • sumInts(5, 5)intenta volver 5 + sumInts(6, 5). Para hacer eso, llama sumInts(6, 5).
  • sumInts(6, 5)devuelve 0 a sumInts(5, 5).</li> <li>sumInts (5, 5) now has a value forsumInts (6, 5) , namely 0. It then returns5 + 0 = 5`.
• sumInts(4, 5)ahora tiene un valor para sumInts(5, 5), es decir, 5. Luego regresa 4 + 5 = 9.

En otras palabras, el valor que se devuelve se forma sumando los valores uno a la vez, tomando cada vez un valor devuelto por una llamada recursiva particular ay sumIntsagregando el valor actual de a. Cuando la recursividad toca fondo, la llamada más profunda devuelve 0. Sin embargo, ese valor no sale inmediatamente de la cadena de llamadas recursivas; en su lugar, simplemente devuelve el valor a la llamada recursiva una capa por encima. De esa manera, cada llamada recursiva simplemente agrega un número más y lo devuelve más arriba en la cadena, culminando con la suma general. Como ejercicio, intente rastrear esto sumInts(2, 5), que es con lo que quería comenzar.

¡Espero que esto ayude!

Tiene algunas buenas respuestas aquí hasta ahora, pero agregaré una más que toma un rumbo diferente.

En primer lugar, he escrito muchos artículos sobre algoritmos recursivos simples que pueden resultarle interesantes; ver

http://ericlippert.com/tag/recursion/

http://blogs.msdn.com/b/ericlippert/archive/tags/recursion/

Esos están en el orden más reciente en la parte superior, así que comience desde abajo.

En segundo lugar, hasta ahora todas las respuestas han descrito la semántica recursiva al considerar la activación de funciones . Que cada, cada llamada hace una nueva activación , y la llamada recursiva se ejecuta en el contexto de esta activación. Esa es una buena forma de pensar en ello, pero hay otra forma equivalente: buscar y reemplazar texto inteligente .

Permítame reescribir su función en una forma un poco más compacta; no piense en esto como si estuviera en un idioma en particular.

s = (a, b) => a > b ? 0 : a + s(a + 1, b)

Espero que tenga sentido. Si no está familiarizado con el operador condicional, es de la forma condition ? consequence : alternativey su significado quedará claro.

Ahora deseamos evaluar.Lo s(2,5) hacemos reemplazando textualmente la llamada con el cuerpo de la función, luego reemplazamos acon 2y bcon 5:

s(2, 5) 
---> 2 > 5 ? 0 : 2 + s(2 + 1, 5)

Ahora evalúe el condicional. Reemplazamos textualmente 2 > 5con false.

---> false ? 0 : 2 + s(2 + 1, 5)

Ahora reemplace textualmente todos los condicionales falsos con la alternativa y todos los condicionales verdaderos con la consecuencia. Solo tenemos condicionales falsos, por lo que reemplazamos textualmente esa expresión con la alternativa:

---> 2 + s(2 + 1, 5)

Ahora, para evitar tener que escribir todos esos +signos, reemplace textualmente la aritmética constante con su valor. (¡Esto es un poco trampa, pero no quiero tener que hacer un seguimiento de todos los paréntesis!)

---> 2 + s(3, 5)

Ahora busque y reemplace, esta vez con el cuerpo de la llamada, 3para ay 5para b. Pondremos el reemplazo de la llamada entre paréntesis:

---> 2 + (3 > 5 ? 0 : 3 + s(3 + 1, 5))

Y ahora seguimos haciendo los mismos pasos de sustitución textual:

---> 2 + (false ? 0 : 3 + s(3 + 1, 5))  
---> 2 + (3 + s(3 + 1, 5))                
---> 2 + (3 + s(4, 5))                     
---> 2 + (3 + (4 > 5 ? 0 : 4 + s(4 + 1, 5)))
---> 2 + (3 + (false ? 0 : 4 + s(4 + 1, 5)))
---> 2 + (3 + (4 + s(4 + 1, 5)))
---> 2 + (3 + (4 + s(5, 5)))
---> 2 + (3 + (4 + (5 > 5 ? 0 : 5 + s(5 + 1, 5))))
---> 2 + (3 + (4 + (false ? 0 : 5 + s(5 + 1, 5))))
---> 2 + (3 + (4 + (5 + s(5 + 1, 5))))
---> 2 + (3 + (4 + (5 + s(6, 5))))
---> 2 + (3 + (4 + (5 + (6 > 5 ? 0 : s(6 + 1, 5)))))
---> 2 + (3 + (4 + (5 + (true ? 0 : s(6 + 1, 5)))))
---> 2 + (3 + (4 + (5 + 0)))
---> 2 + (3 + (4 + 5))
---> 2 + (3 + 9)
---> 2 + 12
---> 14

Todo lo que hicimos aquí fue una simple sustitución textual . Realmente no debería haber sustituido "3" por "2 + 1" y así sucesivamente hasta que tuve que hacerlo, pero pedagógicamente se habría vuelto difícil de leer.

La activación de la función no es más que reemplazar la llamada a la función con el cuerpo de la llamada y reemplazar los parámetros formales con sus argumentos correspondientes. Debe tener cuidado al introducir paréntesis de manera inteligente, pero aparte de eso, es solo un reemplazo de texto.

Por supuesto, la mayoría de los idiomas no implementan la activación como reemplazo de texto, pero lógicamente eso es lo que es.

Entonces, ¿qué es una recursividad ilimitada? ¡Una recursividad donde la sustitución textual no se detiene! Observe cómo finalmente llegamos a un paso en el que no había más sque reemplazar, y entonces pudimos aplicar las reglas de la aritmética.

La forma en que normalmente descubro cómo funciona una función recursiva es mirando el caso base y trabajando hacia atrás. Aquí está la técnica aplicada a esta función.

Primero el caso base:

sumInts(6, 5) = 0

Luego, la llamada justo encima de eso en la pila de llamadas :

sumInts(5, 5) == 5 + sumInts(6, 5)
sumInts(5, 5) == 5 + 0
sumInts(5, 5) == 5

Luego, la llamada justo encima de eso en la pila de llamadas:

sumInts(4, 5) == 4 + sumInts(5, 5)
sumInts(4, 5) == 4 + 5
sumInts(4, 5) == 9

Y así:

sumInts(3, 5) == 3 + sumInts(4, 5)
sumInts(3, 5) == 3 + 9
sumInts(3, 5) == 12

Y así:

sumInts(2, 5) == 2 + sumInts(3, 5)
sumInts(4, 5) == 2 + 12
sumInts(4, 5) == 14

Observe que hemos llegado a nuestra llamada original a la función sumInts(2, 5) == 14

El orden en el que se ejecutan estas llamadas:

sumInts(2, 5)
sumInts(3, 5)
sumInts(4, 5)
sumInts(5, 5)
sumInts(6, 5)

El orden en el que regresan estas llamadas:

sumInts(6, 5)
sumInts(5, 5)
sumInts(4, 5)
sumInts(3, 5)
sumInts(2, 5)

Tenga en cuenta que llegamos a una conclusión sobre cómo opera la función rastreando las llamadas en el orden en que regresan .

Voy a darle una oportunidad.

Ejecutando la ecuación a + sumInts (a + 1, b), mostraré cómo la respuesta final es 14.

//the sumInts function definition
func sumInts(a: Int, b: Int) -> Int {
    if (a > b) {
        return 0
    } else {
        return a + sumInts(a + 1, b)
    }
}

Given: a = 2 and b = 5

1) 2 + sumInts(2+1, 5)

2) sumInts(3, 5) = 12
   i) 3 + sumInts(3+1, 5)
   ii) 4 + sumInts(4+1, 5)
   iii) 5 + sumInts(5+1, 5)
   iv) return 0
   v) return 5 + 0
   vi) return 4 + 5
   vii) return 3 + 9

3) 2 + 12 = 14.

Háganos saber si tiene más preguntas.

Aquí hay otro ejemplo de funciones recursivas en el siguiente ejemplo.

Un hombre acaba de graduarse de la universidad.

t es la cantidad de tiempo en años.

El número total real de años trabajados antes de jubilarse se puede calcular de la siguiente manera:

public class DoIReallyWantToKnow 
{
    public int howLongDoIHaveToWork(int currentAge)
    {
      const int DESIRED_RETIREMENT_AGE = 65;
      double collectedMoney = 0.00; //remember, you just graduated college
      double neededMoneyToRetire = 1000000.00

      t = 0;
      return work(t+1);
    }

    public int work(int time)
    {
      collectedMoney = getCollectedMoney();

      if(currentAge >= DESIRED_RETIREMENT_AGE 
          && collectedMoney == neededMoneyToRetire
      {
        return time;
      }

      return work(time + 1);
    }
}

Y eso debería ser suficiente para deprimir a cualquiera, jajaja. ;-PAGS

Recursión. En Ciencias de la Computación, la recursividad se cubre en profundidad bajo el tema de Autómatas finitos.

En su forma más simple, es una autorreferencia. Por ejemplo, decir que "mi coche es un coche" es una afirmación recursiva. El problema es que la declaración es una recursividad infinita en el sentido de que nunca terminará. La definición en el enunciado de un "automóvil" es que es un "automóvil", por lo que puede ser sustituido. Sin embargo, no hay fin porque en el caso de sustitución, todavía se convierte en "mi coche es un coche".

Esto podría ser diferente si la declaración fuera "mi auto es un Bentley. Mi auto es azul". En cuyo caso, la sustitución de coche en la segunda situación podría ser "bentley", lo que resultaría en "mi bentley es azul". Estos tipos de sustituciones se explican matemáticamente en Ciencias de la Computación a través de gramáticas libres de contexto. .

La sustitución real es una regla de producción. Dado que el enunciado está representado por S y que car es una variable que puede ser un "bentley", este enunciado puede reconstruirse de forma recursiva.

S -> "my"S | " "S | CS | "is"S | "blue"S | ε
C -> "bentley"

Esto se puede construir de múltiples formas, ya que cada una |significa que hay una opción. Sse puede reemplazar por cualquiera de esas opciones, y S siempre comienza vacío. losε medios para terminar la producción. Al igual que Sse pueden reemplazar, también se pueden reemplazar otras variables (solo hay una y esC que representaría "bentley").

Entonces, comenzando por Sestar vacío y reemplazándolo con la primera opción"my"S S convierte en

"my"S

Stodavía se puede sustituir ya que representa una variable. Podríamos elegir "mi" de nuevo, o ε para terminarlo, pero sigamos haciendo nuestra declaración original. Elegimos el espacio que significaS se reemplaza con" "S

"my "S

A continuación, elija C

"my "CS

Y C solo tiene una opción de reemplazo

"my bentley"S

Y el espacio de nuevo para S

"my bentley "S

Y así sucesivamente "my bentley is"S,"my bentley is "S , "my bentley is blue"S,"my bentley is blue" (en sustitución de S ε termina la producción) y hemos construido de forma recursiva nuestra declaración de "mi Bentley es azul".

Piense en la recursividad como estas producciones y reemplazos. Cada paso del proceso reemplaza a su predecesor para producir el resultado final. En el ejemplo exacto de la suma recursiva de 2 a 5, terminas con la producción

S -> 2 + A
A -> 3 + B
B -> 4 + C
C -> 5 + D
D -> 0

Esto se convierte en

2 + A
2 + 3 + B
2 + 3 + 4 + C
2 + 3 + 4 + 5 + D
2 + 3 + 4 + 5 + 0
14

Creo que la mejor manera de entender las funciones recursivas es darse cuenta de que están diseñadas para procesar estructuras de datos recursivas. Pero en su función original sumInts(a: Int, b: Int)que calcula recursivamente la suma de números desde ahasta b, parece no ser una estructura de datos recursiva ... Probemos una versión ligeramente modificada sumInts(a: Int, n: Int)donde nes cuántos números agregará.

Ahora, sumInts es recursivo n, un número natural. Aún no es un dato recursivo, ¿verdad? Bueno, un número natural podría considerarse una estructura de datos recursiva utilizando axiomas de Peano:

enum Natural = {
    case Zero
    case Successor(Natural)
}

Entonces, 0 = cero, 1 = sucesor (cero), 2 = sucesor (sucesor (cero)), y así sucesivamente.

Una vez que tenga una estructura de datos recursiva, tendrá la plantilla para la función. Para cada caso no recursivo, puede calcular el valor directamente. Para los casos recursivos , asume que la función recursiva ya está funcionando y la usa para calcular el caso, pero deconstruyendo el argumento. En el caso de Natural, significa que en lugar de Succesor(n)usaremos n, o de manera equivalente, en lugar de nusaremos n - 1.

// sums n numbers beginning from a
func sumInts(a: Int, n: Int) -> Int {
    if (n == 0) {
        // non recursive case
    } else {
        // recursive case. We use sumInts(..., n - 1)
    }
}

Ahora la función recursiva es más sencilla de programar. En primer lugar, el caso base, n=0. ¿Qué debemos devolver si no queremos sumar números? La respuesta es, por supuesto, 0.

¿Qué pasa con el caso recursivo? ¿Si queremos sumar nnúmeros que empiecen por ay ya tenemos una sumIntsfunción de trabajo que funcione n-1? Bueno, necesitamos agregar ay luego invocar sumIntscon a + 1, así que terminamos con:

// sums n numbers beginning from a
func sumInts(a: Int, n: Int) -> Int {
    if (n == 0) {
        return 0
    } else {
        return a + sumInts(a + 1, n - 1)
    }
}

Lo bueno es que ahora no debería tener que pensar en el bajo nivel de recursividad. Solo necesita verificar que:

• Para los casos base de los datos recursivos, calcula la respuesta sin utilizar la recursividad.
• Para los casos recursivos de los datos recursivos, calcula la respuesta utilizando la recursividad sobre los datos desestructurados.

Puede que le interese la implementación de funciones de Nisan y Schocken . El pdf vinculado es parte de un curso en línea gratuito. Describe la segunda parte de la implementación de una máquina virtual en la que el estudiante debe escribir un compilador de lenguaje de máquina virtual a lenguaje de máquina. La implementación de la función que proponen es capaz de recursividad porque está basada en pilas.

Para presentarle la implementación de la función: considere el siguiente código de máquina virtual:

Si Swift compiló en este lenguaje de máquina virtual, entonces el siguiente bloque de código Swift:

mult(a: 2, b: 3) - 4

se compilaría hasta

push constant 2  // Line 1
push constant 3  // Line 2
call mult        // Line 3
push constant 4  // Line 4
sub              // Line 5

El lenguaje de la máquina virtual está diseñado en torno a una pila global .push constant ninserta un número entero en esta pila global.

Después de ejecutar las líneas 1 y 2, la pila se ve así:

256:  2  // Argument 0
257:  3  // Argument 1

256y 257son direcciones de memoria.

call mult inserta el número de línea de retorno (3) en la pila y asigna espacio para las variables locales de la función.

256:  2  // argument 0
257:  3  // argument 1
258:  3  // return line number
259:  0  // local 0

... y va a la etiqueta function mult. Se multejecuta el código interno . Como resultado de ejecutar ese código, calculamos el producto de 2 y 3, que se almacena en la variable local 0 de la función.

256:  2  // argument 0
257:  3  // argument 1
258:  3  // return line number
259:  6  // local 0

Justo antes de returning de mult, notará la línea:

push local 0  // push result

Empujaremos el producto sobre la pila.

256:  2  // argument 0
257:  3  // argument 1
258:  3  // return line number
259:  6  // local 0
260:  6  // product

Cuando regresamos, sucede lo siguiente:

• Coloque el último valor de la pila en la dirección de memoria del argumento 0 (256 en este caso). Este es el lugar más conveniente para colocarlo.
• Descarte todo en la pila hasta la dirección del argumento 0.
• Vaya al número de línea de retorno (3 en este caso) y luego avance.

Después de regresar, estamos listos para ejecutar la línea 4, y nuestra pila se ve así:

256:  6  // product that we just returned

Ahora colocamos 4 en la pila.

256:  6
257:  4

subes una función primitiva del lenguaje de la máquina virtual. Toma dos argumentos y devuelve su resultado en la dirección habitual: la del argumento 0.

Ahora tenemos

256:  2  // 6 - 4 = 2

Ahora que sabe cómo funciona una llamada de función, es relativamente sencillo comprender cómo funciona la recursividad. Sin magia , solo una pila.

He implementado su sumIntsfunción en este lenguaje de máquina virtual:

function sumInts 0     // `0` means it has no local variables.
  label IF
    push argument 0
    push argument 1
    lte              
    if-goto ELSE_CASE
    push constant 0
    return
  label ELSE_CASE
    push constant 2
    push argument 0
    push constant 1
    add
    push argument 1
    call sumInts       // Line 15
    add                // Line 16
    return             // Line 17
// End of function

Ahora lo llamaré:

push constant 2
push constant 5
call sumInts           // Line 21

El código se ejecuta y llegamos hasta el punto de parada donde lteregresa false. Así es como se ve la pila en este punto:

// First invocation
256:  2   // argument 0
257:  5   // argument 1
258:  21  // return line number
259:  2   // augend
// Second
260:  3   // argument 0
261:  5   // argument 1
262:  15  // return line number
263:  3   // augend
// Third
264:  4   // argument 0
265:  5   // argument 1
266:  15  // return line number
267:  4   // augend
// Fourth
268:  5   // argument 0
269:  5   // argument 1
270:  15  // return line number
271:  5   // augend
// Fifth
272:  6   // argument 0
273:  5   // argument 1
274:  15  // return line number
275:  0   // return value

Ahora "desenrollemos" nuestra recursividad. return0 y vaya a la línea 15 y avance.

271:  5
272:  0

Línea 16: add

271:  5

Línea 17: return5 y vaya a la línea 15 y avance.

267:  4
268:  5

Línea 16: add

267:  9

Línea 17: return9 y vaya a la línea 15 y avance.

263:  3
264:  9

Línea 16: add

263:  12

Línea 17: return12 y vaya a la línea 15 y avance.

259:  2
260:  12

Línea 16: add

259:  14

Línea return17:14 y vaya a la línea 21 y avance.

256:  14

Ahí tienes. Recursión: glorificado goto.

Un consejo realmente bueno que encontré al aprender y comprender realmente la recursividad es dedicar un tiempo a aprender un idioma que no tiene ninguna forma de construcción de bucle que no sea la recursividad. De esa manera, obtendrá una gran idea de cómo USAR la recursividad a través de la práctica.

Seguí http://www.htdp.org/ que, además de ser un tutorial de Scheme, también es una gran introducción sobre cómo diseñar programas en términos de arquitectura y diseño.

Pero básicamente, necesitas invertir algo de tiempo. Sin una comprensión "firme" de la recursividad, ciertos algoritmos, como el retroceso, siempre le parecerán "difíciles" o incluso "mágicos". Así que persevera. :-RE

¡Espero que esto ayude y buena suerte!

Ya hay muchas buenas respuestas. Todavía lo estoy intentando.
Cuando se llama, una función obtiene un espacio de memoria asignado, que se apila en el espacio de memoria de la función de llamada. En este espacio de memoria, la función mantiene los parámetros que se le pasan, las variables y sus valores. Este espacio de memoria desaparece junto con la llamada de retorno final de la función. Como dice la idea de pila, el espacio de memoria de de la función de llamada ahora se activa.

Para llamadas recursivas, la misma función obtiene múltiples espacios de memoria apilados uno sobre otro. Eso es todo. La simple idea de cómo funciona la pila en la memoria de una computadora debería ayudarlo a comprender cómo ocurre la recursividad en la implementación.

Un poco fuera de tema, lo sé, pero ... intente buscar la recursividad en Google ... Verá con un ejemplo lo que significa :-)

Las versiones anteriores de Google devolvieron el siguiente texto (citado de memoria):

Recursividad

Ver recursividad

El 10 de septiembre de 2014, se actualizó el chiste sobre la recursividad:

Recursividad

Quiso decir: Recursion

Para otra respuesta, vea esta respuesta .

Piense en la recursividad como múltiples clones haciendo lo mismo ...

Pides clonar [1]: "suma números entre 2 y 5"

+ clone[1]               knows that: result is 2 + "sum numbers between 3 and 5". so he asks to clone[2] to return: "sum numbers between 3 and 5"
|   + clone[2]           knows that: result is 3 + "sum numbers between 4 and 5". so he asks to clone[3] to return: "sum numbers between 4 and 5"
|   |   + clone[3]       knows that: result is 4 + "sum numbers between 5 and 5". so he asks to clone[4] to return: "sum numbers between 5 and 5"
|   |   |   + clone[4]   knows that: result is 5 + "sum numbers between 6 and 5". so he asks to clone[5] to return: "sum numbers between 6 and 5"
|   |   |   |   clone[5] knows that: he can't sum, because 6 is larger than 5. so he returns 0 as result.
|   |   |   + clone[4]   gets the result from clone[5] (=0)  and sums: 5 + 0,  returning 5
|   |   + clone[3]       gets the result from clone[4] (=5)  and sums: 4 + 5,  returning 9
|   + clone[2]           gets the result from clone[3] (=9)  and sums: 3 + 9,  returning 12
+ clone[1]               gets the result from clone[2] (=12) and sums: 2 + 12, returning 14

¡¡y voilá!!

Muchas de las respuestas anteriores son muy buenas. Sin embargo, una técnica útil para resolver la recursividad es deletrear primero lo que queremos hacer y codificar como lo resolvería un humano. En el caso anterior, queremos resumir una secuencia de enteros consecutivos (usando los números de arriba):

2, 3, 4, 5  //adding these numbers would sum to 14

Ahora, tenga en cuenta que estas líneas son confusas (no incorrectas, sino confusas).

if (a > b) {
    return 0 
}

¿Por qué la prueba a>b? Y por quéreturn 0

Cambiemos el código para reflejar más de cerca lo que hace un humano

func sumInts(a: Int, b: Int) -> Int {
  if (a == b) {
    return b // When 'a equals b' I'm at the most Right integer, return it
  }
  else {
    return a + sumInts(a: a + 1, b: b)
  }
}

¿Podemos hacerlo aún más humano? ¡Si! Normalmente sumamos de izquierda a derecha (2 + 3 + ...). Pero la recursividad anterior se suma de derecha a izquierda (... + 4 + 5). Cambie el código para reflejarlo ( -puede ser un poco intimidante, pero no mucho)

func sumInts(a: Int, b: Int) -> Int {
  if (a == b) {
    return b // When I'm at the most Left integer, return it
  }
  else {
    return sumInts(a: a, b: b - 1) + b
  }
}

Algunos pueden encontrar esta función más confusa ya que estamos comenzando desde el extremo 'lejano', pero practicar puede hacer que se sienta natural (y es otra buena técnica de 'pensamiento': probar 'ambos' lados al resolver una recursividad). Y de nuevo, la función refleja lo que hace un ser humano (¿la mayoría?): Toma la suma de todos los enteros de la izquierda y suma el "siguiente" entero de la derecha.

Estaba teniendo dificultades para entender la recursividad, luego encontré este blog y ya vi esta pregunta, así que pensé que debía compartirla. Debes leer este blog, lo encontré extremadamente útil, explica con stack e incluso explica cómo dos recursiones funcionan con stack paso a paso. Le recomiendo que primero comprenda cómo funciona la pila, que se explica muy bien aquí: viaje a la pila

then now you will understand how recursion works now take a look of this post: Comprender la recursividad paso a paso

Es un programa:

def hello(x):
    if x==1:
        return "op"
    else:
        u=1
        e=12
        s=hello(x-1)
        e+=1
        print(s)
        print(x)
        u+=1
    return e

hello(3)

La recursividad comenzó a tener sentido para mí cuando dejé de leer lo que otros dicen al respecto o de verlo como algo que puedo evitar y simplemente escribí código. Encontré un problema con una solución e intenté duplicar la solución sin mirar. Solo miré la solución cuando me quedé atascado sin poder hacer nada. Luego volví a intentar duplicarlo. Hice esto nuevamente en múltiples problemas hasta que desarrollé mi propia comprensión y sentido de cómo identificar un problema recursivo y resolverlo. Cuando llegué a este nivel, comencé a inventar problemas y a resolverlos. Eso me ayudó más. A veces, las cosas solo se pueden aprender probándolo por su cuenta y luchando; hasta que "lo consigas".

Déjame decirte con un ejemplo de la serie de Fibonacci, Fibonacci es

t (n) = t (n - 1) + n;

si n = 0 entonces 1

así que vamos a ver cómo funciona la recursividad, acabo de reemplazar nen t(n)con n-1y así sucesivamente. parece:

t (n-1) = t (n - 2) + n + 1;

t (n-1) = t (n - 3) + n + 1 + n;

t (n-1) = t (n - 4) + n + 1 + n + 2 + n;

.

.

.

t (n) = t (nk) + ... + (nk-3) + (nk-2) + (nk-1) + n;

sabemos si t(0)=(n-k)es igual a 1entonces, n-k=0así n=kque lo reemplazamos kcon n:

t (n) = t (nn) + ... + (n-n + 3) + (n-n + 2) + (n-n + 1) + n;

si omitimos n-nentonces:

t (n) = t (0) + ... + 3 + 2 + 1 + (n-1) + n;

también lo 3+2+1+(n-1)+nes el número natural. calcula comoΣ3+2+1+(n-1)+n = n(n+1)/2 => n²+n/2

el resultado de fib es: O(1 + n²) = O(n²)

Esta es la mejor manera de entender la relación recursiva