Recursión: Detrás de las escenas

Si bien es sabido que la recursión es “un método que se llama a sí mismo”, me inclino a preguntarme qué está sucediendo realmente. Tomemos el ejemplo factorial clásico:

public static int fact(int n) { if(n == 0) return 1; else return n * fact(n - 1); } 

hecho (5);

Entiendo que es un poco como esto: (el signo igual indica lo que está sucediendo cuando se llama a la función para ese valor)

http://postimg.org/image/4yjalakcb/

¿Por qué la recursión funciona así? ¿Qué aspecto de una computadora hace que funcione a través de sí mismo hacia atrás como tal? ¿Qué está pasando detrás de las escenas?

Como estudiante, siento que la recursión que se nos enseña es superficial y general. Quiero que la excelente comunidad esté aquí para ayudarme a entenderlo en el nivel de la máquina. ¡Gracias!

Aquí está la breve descripción de lo que sucede, siempre que llame a un método:

  • Se asigna un marco para ese método desde la stack.
  • El marco contiene, todas las variables locales, parámetros, valores de retorno del método.
  • Ese marco se coloca sobre la parte superior del marco del método actual, que invoca este método.
  • Cuando el método vuelve, el marco relacionado con ese método se extrae de la stack, y el método de llamada vuelve a la acción, tomando el valor de retorno, si corresponde, del método anterior.

Puede obtener más información sobre los marcos aquí – Especificaciones JVM – Marcos .

En caso de recursión, sucede lo mismo. Solo por el momento, olvida que estás lidiando con la recursión, y toma cada llamada recursiva como una llamada a un método diferente. Entonces, en caso factorial , la stack crecería así:

 fact(5) 5 * fact(4) 4 * fact(3) 3 * fact(2) 2 * fact(1) 1 * fact(0) // Base case reached. Stack starts unwinding. 2 * 1 * 1 3 * 2 * 1 * 1 4 * 3 * 2 * 1 * 1 5 * 4 * 3 * 2 * 1 * 1 == Final result 

Si rastrea las llamadas de función, verá cómo funciona.

P.ej

fact(3) devolverá 3 * fact(2) . Así que Java llamará fact(2) .

fact(2) devolverá 2 * fact(1) . Así que Java llamará fact(1) .

fact(1) devolverá 1 * fact(0) . Así que Java llamará fact(0) .

fact(0) devolverá 1 .

Entonces el fact(1) devolverá 1 * 1 = 1 .

Entonces el fact(2) devolverá 2 * 1 = 2 .

Entonces el fact(3) devolverá 3 * 2 = 6 .


Java llama al método recursivo como lo haría con cualquier otro método.

Es posible que haya oído hablar de algo llamado “The Stack”. Es lo que se usa para almacenar estados de métodos.

Creo que también almacena la línea de llamada, para que la función pueda volver a su interlocutor.

Así que supongamos que tiene su llamada a una función recursiva

  - int $input = 5 - stack.Push L - GOTO FOO - Label L 

su función recursiva (sin un caso base) podría parecerse a la siguiente

  - Label FOO - int in = $input - input = in - 1 - stack.Push in - stack.Push L2 - goto FOO - Label L2 - in = stack.Pop in - output *= in - goto stack.POP 

Tal vez lo siguiente te ayude a entender. A la computadora no le importa si llama a la misma función, es solo computación. No hay nada mágico en la recursión una vez que entiendes lo que es y por qué funciona con muchas cosas, como listas, números naturales, etc., quienes son recursivos por su propia estructura.

  1. Definición: El factorial de 0 es 1.
  2. Definición: El factorial de un número n mayor que 0 es el producto de ese número y el factorial de su predecesor.

Por lo tanto

 5! = 5*4! = 5*4*3! = 5*4*3*2! = 5*4*3*2*1! = 5*4*3*2*1*0! = 5*4*3*2*1*1 = 120 

Entonces, si alguna vez has oído hablar de la prueba por inducción, es así:

  1. Comprobamos alguna propiedad para un caso base.
  2. Probamos que, si la propiedad es verdadera para n, entonces será verdadera para el sucesor de n.
  3. Llegamos a la conclusión de que esta es la prueba de que la propiedad es válida para el caso base y todos los casos sucesivos.

Ejemplo: ¡Prueba por inducción de que el cuadrado de un número par es un múltiplo de 4!

  1. El cuadrado de 0 es 0, y es un múltiplo de 4.
  2. Sea n un número par, cuyo cuadrado n² es un múltiplo de 4. Entonces (2+n)*(2+n) = 4+2n+2n+n² . Este es un múltiplo de 4, porque n² fue por nuestra suposición, 4 es uno y 2n+2n = 4n también es un múltiplo de 4 y la sum de los múltiplos de 4 es un múltiplo de 4 por ley distributiva: 4a + 4b = 4(a+b)
  3. QED La propiedad es válida para 0 (nuestro caso base) y para (2 + n), siempre que sea válida para n. Por lo tanto, se mantiene para 2, 4, 6, 8 …. y todos los demás números pares.

(Una prueba más fácil sería observar que (2a)² = 4*a*a , que es un múltiplo de 4.)

Escribir un progtwig recursivo es muy similar a hacer una prueba por inducción:

  1. Escribimos el cómputo para el caso base.
  2. Para el caso no básico, sabemos cómo podemos calcular el resultado (por ejemplo, ¡sabemos que n! = n * (n-1)! , Así que lo escribimos simplemente hacia abajo , ya que la función que necesitamos es la que somos solo escribo
  3. Podemos concluir que nuestro progtwig calculará el valor correcto para el caso base y cualquier sucesor del caso base. Si 678! sin embargo, no computa la respuesta correcta, entonces tiene que ver con el hecho de que usamos un tipo de datos como int que no es muy adecuado para grandes números (o, para decirlo de otra manera, calcula todo el módulo 2 ^ 32) y en Además, con un software que insiste en interpretar la mitad de los números disponibles como negativos.

La razón por la que esto funciona no tiene nada que ver con el hardware de la computadora o el lenguaje de progtwigción: es, como dije antes, una consecuencia de la estructura recursiva de los elementos (listas, árboles, conjuntos, números naturales) a la mano.

Un error común que cometen los recién llegados es ignorar el caso base y perderse en la complejidad. Siempre sugiero comenzar con el caso base, una vez que tenga esto, puede asumir que la función existe, y solo puede usarla en los casos más complejos.