function - recursividad - Comprender cómo funcionan las funciones recursivas

funciones recursivas en c

Question

Como el título explica, tengo una pregunta de programación fundamental que todavía no he podido realizar. Filtrando todo (extremadamente inteligente) "Para comprender la recursión, primero debe comprender la recursión". respuestas de varios hilos en línea, todavía no lo estoy obteniendo del todo.

Entendiendo que cuando nos enfrentamos a no saber lo que no sabemos, podemos tender a hacer las preguntas incorrectas o hacer las preguntas correctas de forma incorrecta. Compartiré lo que "pienso" que es mi pregunta con la esperanza de que alguien con una perspectiva similar pueda compartir ¡un poco de conocimiento que ayudará a encender la bombilla recursiva para mí!

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 hangups:

1. La función se llama recursivamente 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 de retorno fuera 0, lo que obviamente es incorrecto.

2. Imprimir el valor de ''a'' en cada iteración arroja un valor que yo esperaría: 2, 3, 4, 5 (en este punto 5 + 1> b que cumple con la primera condición: a> b) pero todavía no lo hago t ver 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 qué está sucediendo más que solo implícitamente.

Si alguien puede 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) = 14 , estaría siempre en deuda con usted .

Answer 1

1.La función se llama recursivamente 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 de retorno fuera 0, lo que obviamente es incorrecto.

sumInts(2,5) es lo que sumInts(2,5) los computadores informáticos sumInts(2,5) si fuera capaz de:

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 ve, algunos llaman a la función sumInts realidad devuelve 0, pero este no es el valor final porque la computadora todavía tiene que sumar 5 a ese 0, luego 4 al resultado, luego 3, luego 2, como se describe en las cuatro últimas oraciones de los pensamientos de nuestra computadora. Tenga en cuenta que en la recursión, la computadora no solo tiene que calcular la llamada recursiva, sino que también debe recordar qué hacer con el valor devuelto por la llamada recursiva. Hay un área especial de la memoria de la computadora llamada la 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 la pila dando su nombre a nuestro sitio más querido.

Su afirmación parece hacer la suposición implícita de que la computadora olvida qué era al hacer una llamada recursiva, pero no es así, esta es la razón por la cual su conclusión no coincide con su observación.

2. Al imprimir el valor de ''a'' en cada iteración, se obtiene un valor que yo esperaría: 2, 3, 4, 5 (en cuyo punto 5 + 1> b cumple la primera condición: a> b) pero aún así no veo cómo se logra el valor de 14.

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

Answer 2

Aquí tienes algunas buenas respuestas 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 resultar interesantes; ver

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

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

Esos son los más nuevos en el orden superior, así que comience desde abajo.

En segundo lugar, hasta ahora todas las respuestas han descrito la semántica recursiva considerando la activación de la función . Que cada llamada realiza una nueva activación y que la llamada recursiva se ejecuta en el contexto de esta activación. Esa es una buena manera de pensarlo, pero hay otra manera equivalente: buscar y reemplazar texto inteligente .

Déjame reescribir tu función en una forma un poco más compacta; no piense que esto está 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, ¿tiene la condition ? consequence : alternative forma condition ? consequence : alternative condition ? consequence : alternative y su significado quedará claro.

Ahora deseamos evaluar s(2,5) Lo hacemos haciendo un reemplazo textual de la llamada con el cuerpo de la función, luego reemplazamos a con 2 y b con 5 :

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

Ahora evalúa el condicional. Reemplazamos textualmente 2 > 5 por false .

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

Ahora reemplaza 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 que tenga que escribir todos esos signos + , sustituya textualmente la aritmética constante por su valor. (Esto es un poco engañoso, ¡pero no quiero tener que seguir todos los paréntesis!)

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

Ahora busca y reemplaza, esta vez con el cuerpo para la llamada, 3 para a y 5 para b. Pondremos el reemplazo de la llamada entre paréntesis:

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

Y ahora seguimos haciendo esos 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 simplemente 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 función no es más que reemplazar la llamada de función con el cuerpo de la llamada y reemplazar los parámetros formales con sus argumentos correspondientes. Debes tener cuidado al introducir paréntesis de forma 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 recursión sin límites? ¡Una recursión donde la sustitución textual no se detiene! Observe cómo eventualmente llegamos a un paso donde no había más s para reemplazar, y entonces simplemente podíamos aplicar las reglas para la aritmética.

Answer 3

Creo que la confusión se deriva de pensar que se llama "la misma función" muchas veces. Si lo considera como "muchas copias de la misma función que se llama", 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 parte de la confusión, creo que será más fácil deletrear la recursión en inglés. Lee esta linea:

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

como "devolver 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í mismo con un incremento en 1, hasta que se cumpla la condición a> b.

Para cuando llegue a la condición a> b, es decir, tiene una (potencialmente arbitraria) gran cantidad de copias de la función, todas en el medio de ejecución, todas esperando el resultado de la siguiente copia para averiguar qué debería agregar a ''a''.

(edit: 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 colgará tu programa si es demasiado grande. El compilador puede optimizarlo en algunos casos, pero el agotador espacio de la pila es una limitación significativa y desafortunada de las funciones recursivas en muchos idiomas)

Answer 4

Creo que la mejor manera de entender las funciones recursivas es darse cuenta de que están hechas para procesar estructuras recursivas de datos. Pero en sus funciones originales sumInts(a: Int, b: Int) que calcula de forma recursiva la suma de números de sumInts(a: Int, b: Int) b , parece que no es una estructura de datos recursiva ... Probemos una versión ligeramente modificada sumInts(a: Int, n: Int) donde n es la cantidad de números que agregará.

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

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

Entonces, 0 = Cero, 1 = Succesor (Cero), 2 = Succesor (Succesor (Cero)), y así sucesivamente.

Una vez que tiene una estructura de datos recursiva, tiene la plantilla para la función. Para cada caso no recursivo, puede calcular el valor directamente. Para los casos recursivos supones que la función recursiva ya está funcionando y la utilizas para calcular el caso, pero deconstruyendo el argumento. En el caso de Natural, significa que en lugar de Succesor(n) usaremos n , o equivalentemente, en lugar de n usaremos 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 simple de programar. Primero, el caso base, n=0 . ¿Qué deberíamos devolver si no queremos agregar números? La respuesta es, por supuesto 0.

¿Qué pasa con el caso recursivo? Si queremos agregar n números que comiencen con a y ya tenemos una función de trabajo sumInts que funcione para n-1 ? Bueno, necesitamos agregar a y luego invocar sumInts con 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ías necesitar pensar en el bajo nivel de recursividad. Solo necesita verificar que:

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

Answer 5

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

Primero el caso base:

sumInts(6, 5) = 0

Entonces 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

Entonces 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 que se ejecutan estas llamadas:

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

El orden en que estas llamadas regresan:

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 funciona la función al rastrear las llamadas en el orden en que regresan .

Answer 6

La recursividad es un tema difícil de entender y no creo que pueda hacer justicia aquí. En cambio, trataré de enfocarme en la pieza de código que tienes aquí e intentar 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 enteros de aab, inclusive. Para su ejemplo, desea la suma de los números del 2 al 5, inclusive, que es

2 + 3 + 4 + 5

Al tratar de resolver un problema recursivamente, uno de los primeros pasos debería ser descubrir cómo descomponer el problema en un problema más pequeño con la misma estructura. Supongamos que quiere resumir 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) pasa a ser la suma de todos los enteros entre 3 y 5, inclusive. En otras palabras, si quiere saber la suma de todos los enteros entre 2 y 5, comience por calcular la suma de todos los enteros entre 3 y 5, luego agregue 2.

Entonces, ¿cómo se calcula la suma de todos los 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 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 enteros entre 4 y 5, luego agregarías 3.

¡Hay un patrón aquí! Si desea calcular la suma de los enteros entre ayb, inclusive, puede hacer lo siguiente. Primero, calcule la suma de los enteros entre a + 1 y b, inclusive. Luego, agregue un a ese total. Notarás que "calcular la suma de los enteros entre a + 1 yb, inclusive" es casi el mismo tipo de problema que estamos tratando de resolver, pero con parámetros ligeramente diferentes. En lugar de computar de aa b, inclusive, estamos computando de a + 1 a b, inclusive. Ese es el paso recursivo: para resolver el problema más grande ("suma de aa 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 un paso en esto:

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

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

Por supuesto, este enfoque no funcionará en sí mismo. Por ejemplo, ¿cómo calcularías la suma de todos los enteros entre 5 y 5 inclusive? Bueno, usando nuestra lógica actual, calcularías la suma de todos los enteros entre 6 y 5, inclusive, luego sumar 5. Entonces, ¿cómo calculamos 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 agregarías 6. Verás un problema aquí - ¡esto sigue y sigue!

En la resolución recursiva de problemas, debe haber alguna forma de dejar de simplificar el problema y, en su lugar, resolverlo directamente. Por lo general, encontrará un caso simple en el que la respuesta se puede determinar de inmediato, luego estructure su solución para resolver casos simples directamente cuando surjan. Esto generalmente se llama un caso base o una base recursiva .

Entonces, ¿cuál es el caso base en este problema en particular? Cuando estás sumando números enteros de a hasta b, inclusive, si resulta ser más grande que b, entonces la respuesta es 0 - ¡no hay ningún número 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 enteros entre a + 1 y b.
   2. Agregue un para obtener la respuesta.

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

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

Observe que hay casi exactamente un mapa uno a uno entre la solución descrita en el pseudocódigo y este código real. El primer paso es el caso base: en caso de que solicite la suma de un rango de números vacío, obtiene 0. De lo contrario, calcule la suma entre a + 1 y b, luego vaya agregue a.

Hasta ahora, he dado solo una idea de alto nivel detrás del código. Pero tuviste otras dos preguntas muy buenas. Primero, ¿por qué esto no siempre devuelve 0, dado que la función dice que devuelve 0 si a> b? Segundo, ¿de dónde viene realmente el 14? Veamos esto a su vez.

Probemos un caso muy, muy simple. ¿Qué pasa si llamas a sumInts(6, 5) ? En este caso, siguiendo el código, verá que la función simplemente devuelve 0. Eso es lo que hay que hacer, a - no hay ningún número en el rango. Ahora, intenta algo más duro. ¿Qué sucede cuando llamas a sumInts(5, 5) ? Bueno, esto es lo que sucede:

1. Usted llama a sumInts(5, 5) . Caemos en la rama else , que devuelve el valor de `a + sumInts (6, 5).
2. Para que los sumInts(5, 5) determinen qué son los sumInts(6, 5) , debemos pausar lo que estamos haciendo y hacer una llamada a los sumInts(6, 5) .
3. sumInts(6, 5) . Entra en la rama if y devuelve 0 . Sin embargo, esta instancia de sumInts fue llamada por sumInts(5, 5) , por lo que el valor devuelto se comunica a los sumInts(5, 5) , no al llamante de nivel superior.
4. sumInts(5, 5) ahora pueden calcular 5 + sumInts(6, 5) para recuperar 5 . Luego lo devuelve al llamador de nivel superior.

Observe cómo el valor 5 se formó aquí. Comenzamos con una llamada activa a sumInts . Eso disparó otra llamada recursiva, y el valor devuelto por esa llamada comunicó la información a los sumInts(5, 5) . La llamada a sumInts(5, 5) luego hizo un cálculo 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 devolver 4 + sumInts(5, 5) . Para hacer eso, llama a sumInts(5, 5) .
  • sumInts(5, 5) intenta devolver 5 + sumInts(6, 5) . Para hacer eso, llama sumInts(6, 5) .
  • sumInts(6, 5) devuelve 0 de nuevo a sumInts(5, 5).</li> <li> sumInts (5, 5) now has a value for sumInts (6, 5) , namely 0. It then returns 5 + 0 = 5`.
• sumInts(4, 5) ahora tiene un valor para sumInts(5, 5) , es decir, 5. Luego devuelve 4 + 5 = 9 .

En otras palabras, el valor que se devuelve se forma sumando los valores uno a la vez, cada vez tomando un valor devuelto por una llamada recursiva particular a los sumInts y agregando 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 llamada recursiva; en su lugar, simplemente devuelve el valor a la llamada recursiva una capa por encima de ella. De esta forma, cada llamada recursiva solo agrega un número más y lo devuelve más arriba en la cadena, culminando con la suma general. Como un ejercicio, trate de encontrar esto para las sumInts(2, 5) , que es con lo que quería comenzar.

¡Espero que esto ayude!

Answer 7

Para entender la recursión debes pensar en el problema de una manera diferente. En lugar de una gran secuencia lógica de pasos que tiene sentido como un todo, en su lugar se toma un gran problema y se divide en problemas más pequeños y los resuelve; una vez que tiene una respuesta para los problemas secundarios, combina los resultados de los problemas secundarios para hacer el solución al problema más grande. Piensa en ti y tus amigos que necesitan contar la cantidad de canicas en un cubo grande. Cada uno toma un cubo más pequeño e irá a contarlos individualmente y cuando termine, agregue los totales juntos. Bueno, ahora, si cada uno de ustedes encuentra un amigo y divide los cubos aún más, entonces solo necesita esperar a que estos otros amigos descifrar sus totales, devolvérselos a cada uno de ustedes y agregarlos. Y así. El caso especial es cuando solo obtienes 1 mármol para contar, entonces simplemente lo devuelves y dices 1. deja que las otras personas encima de ti hagan lo que has hecho.

Debe recordar que cada vez que la función se llama recursivamente crea un nuevo contexto con un subconjunto del problema, una vez que esa parte se resuelve, se devuelve para que la iteración anterior pueda completarse.

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 se hayan ejecutado los sumInts (a: 6, b: 5), los resultados se pueden calcular para que vuelvan a la cadena con los resultados que obtiene:

 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 recursión:

 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 

Answer 8

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

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

If Swift compiled to this virtual machine language, then the following block of Swift code:

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

would compile down to

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

The virtual machine language is designed around a global stack . push constant n pushes an integer onto this global stack.

After executing lines 1 and 2, the stack looks like:

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

256 and 257 are memory addresses.

call mult pushes the return line number (3) onto the stack and allocates space for the function''s local variables.

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

...and it goes-to the label function mult . The code inside mult is executed. As a result of executing that code we compute the product of 2 and 3, which is stored in the function''s 0th local variable.

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

Just before return ing from mult, you will notice the line:

push local 0  // push result

We will push the product onto the stack.

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

When we return, the following happens:

• Pop the last value on the stack to the memory address of the 0th argument (256 in this case). This happens to be the most convenient place to put it.
• Discard everything on the stack up to the address of the 0th argument.
• Go-to the return line number (3 in this case) and then advance.

After returning we are ready to execute line 4, and our stack looks like this:

256:  6  // product that we just returned

Now we push 4 onto the stack.

256:  6
257:  4

sub is a primitive function of the virtual machine language. It takes two arguments and returns its result in the usual address: that of the 0th argument.

Ahora tenemos

256:  2  // 6 - 4 = 2

Now that you know how a function call works, it is relatively simple to understand how recursion works. No magic , just a stack.

I have implemented your sumInts function in this virtual machine language:

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

Now I will call it:

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

The code executes and we get all the way to the stopping point where lte returns false . This is what the stack looks like at this point:

// 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

Now let''s "unwind" our recursion. return 0 and goto line 15 and advance.

271:  5
272:  0

Line 16: add

271:  5

Line 17: return 5 and goto line 15 and advance.

267:  4
268:  5

Line 16: add

267:  9

Line 17: return 9 and goto line 15 and advance.

263:  3
264:  9

Line 16: add

263:  12

Line 17: return 12 and goto line 15 and advance.

259:  2
260:  12

Line 16: add

259:  14

Line 17: return 14 and goto line 21 and advance.

256:  14

Ahí tienes. Recursion: Glorified goto .

Answer 9

Recursion En Informática, la recursividad se trata en profundidad bajo el tema de Finite Automata.

En su forma más simple, es una auto referencia. Por ejemplo, decir que "mi automóvil es un automóvil" es una afirmación recursiva. El problema es que la afirmación es una recursión infinita en el sentido de que nunca terminará. La definición en la declaración de un "automóvil" es que es un "automóvil", por lo que puede ser sustituido. Sin embargo, no tiene fin porque en el caso de la sustitución, sigue siendo "mi automóvil es un automóvil".

Esto podría ser diferente si la declaración fuera "mi coche es un bentley. Mi auto es azul". En tal caso, la sustitución en la segunda situación por el automóvil podría ser "bentley", lo que da como resultado "mi bentley es azul". Estos tipos de sustituciones se explican matemáticamente en Informática a través de Gramáticas sin contexto .

La sustitución real es una regla de producción. Dado que la declaración está representada por S y que el automóvil es una variable que puede ser un "bentley", esta afirmación puede reconstruirse recursivamente.

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

Esto se puede construir de múltiples maneras, ya que cada | significa que hay una elección. S puede ser reemplazado por cualquiera de esas elecciones, y S siempre comienza vacío. El ε significa terminar la producción. Así como S puede ser reemplazado, también lo pueden hacer otras variables (solo hay una y es C lo que representaría "bentley").

Así que comenzando con S siendo vacío, y reemplazándolo con la primera opción "my"S S convierte

"my"S

S todavía puede ser sustituido ya que representa una variable. Podríamos elegir "mi" otra vez, o ε para finalizarlo, pero continuemos haciendo nuestra declaración original. Elegimos el espacio que significa que S se reemplaza con " "S

"my "S

A continuación, elijamos C

"my "CS

Y C solo tiene una opción para reemplazar

"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" , "my bentley is blue" (reemplazando S por ε termina la producción) y recursivamente hemos construido nuestra declaración "my bentley" es azul".

Piense en la recursividad como estas producciones y reemplazos. Cada paso en el 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

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

Answer 10

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 en la universidad.

t es la cantidad de tiempo en años.

La cantidad 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 lo suficiente para deprimir a cualquiera, jajaja. ;-PAG

Answer 11

A little bit off-topic, I know, but... try looking up recursion in Google... You''ll see by example what it means :-)

Earlier versions of Google returned the following text (cited from memory):

Recursion

See Recursion

On September 10th 2014, the joke about recursion has been updated:

Recursion

Did you mean: Recursion

For another reply, see this answer .

Answer 12

I was having hard time to understanding recursion then i found this blog and i already seen this question so i thought i must have to share . You must read this blog i found this extremely helpful it explain with stack and even it explain how two recursion works with stack step by step. I recommend you first understand how stack works which it explain very well here : journey-to-the-stack

then now you will understand how recursion works now take a look of this post : Understand recursion step by step

Its a program :

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)

journey-to-the-stack

Answer 13

Many of the answers above are very good. A useful technique for solving recursion though, is to spell out first what we want to do and code as a human would solve it . In the above case, we want to sum up a sequence of consecutive integers (using the numbers from above):

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

Now, note that these lines are confusing (not wrong, but confusing).

if (a > b) {
    return 0 
}

Why the test a>b ?, and why return 0

Let''s change the code to reflect more closely what a human does

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)
  }
}

Can we do it even more human like? ¡Sí! Usually we sum up from left to right (2+3+...). But the above recursion is summing from right to left (...+4+5). Change the code to reflect it (The - can be a little intimidating, but not much)

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
  }
}

Some may find this function more confusing since we are starting from the ''far'' end, but practicing can make it feel natural (and it is another good ''thinking'' technique: Trying ''both'' sides when solving a recursion). And again, the function reflects what a human (most?) does: Takes the sum of all left integers and adds the ''next'' right integer.

Answer 14

One really good tip I came across in learning and really understanding recursion is to spend some time learning a language that doesn''t have any form of loop construct other than via recursion. That way you''ll get a great feel for how to USE recursion via practice.

I followed http://www.htdp.org/ which, as well as being a Scheme tutorial, is also a great introduction on how to design programs in terms of the architecture and design.

But basically, you need to invest some time. Without a ''firm'' grasp of recursion certain algorithms, such as backtracking, will always seem ''hard'' or even ''magic'' to you. So, persevere. :-RE

I hope this helps and Good Luck!

Answer 15

Recursion started making sense to me when I stopped reading what others say about it or seeing it as something I can avoid and just wrote code. I found a problem with a solution and tried to duplicate the solution without looking. I only looked at the solution when I got helplessly stuck. Then I went back at trying to duplicate it. I did this again on multiple problems until I developed my own understanding and sense of how to identify a recursive problem and solve it. When I got to this level, I started making up problems and solving them. That helped me more. Sometimes, things can only be learned by trying it out on your own and struggling; until you “get it”.

Answer 16

There are already a lot of good answers. Still I am giving a try.
When called, a function get a memory-space allotted, which is stacked upon the memory-space of the caller function. In this memory-space, the function keeps the parameters passed to it, the variables and their values. This memory-space vanishes along with the ending return call of the function. As the idea of stack goes, the memory-space of the caller function now becomes active.

For recursive calls, the same function gets multiple memory-space stacked one upon another. Eso es todo. The simple idea of how stack works in memory of a computer should get you through the idea of how recursion happens in implementation.

Answer 17

Think recursion as a multiple clones doing same thing...

You ask to clone[1]: "sum numbers between 2 and 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

and voilá!!