¿Cómo funciona la recursión aquí?

Question

Código 1:

public static int fibonacci (int n){ 
    if (n == 0 || n == 1) { 
     return 1; 
    } else { 
     return fibonacci (n-1) + fibonacci (n-2); 
    }   
} 

¿Cómo se puede utilizar fibonacci si usted no ha conseguido hacer que explica de qué se trata? He sido capaz de entender el uso de la recursividad en otros casos como éste:

Código 2:

class two 
{ 
    public static void two (int n) 
    { 
     if (n>0) 
     { 
      System.out.println (n) ; 
      two (n-1) ; 
     } 
     else 
     { 
      return ; 
     } 
    } 

    public static void main (String[] arg) 
    { 
     two (12) ; 
    } 
} 

En el caso del código 2, sin embargo, n llegará a alcanzar un punto en el que no lo hace satisface n>0 y el método dejará de llamarse recursivamente. Sin embargo, en el caso del código 2, no veo cómo podría obtenerse de 1 si n=1 fuera el punto de partida para 2 y 3 y 5 y así sucesivamente. Además, no veo cómo funcionaría la línea return fibonacci (n-1) + fibonacci (n-2) ya que fibonacci (n-2) tiene que contener en cierto sentido fibonacci (n-1) para funcionar, pero todavía no está allí.

El libro que estoy viendo dice que funcionará. ¿Como funciona?

Answer 1

Bueno, dejando de lado lo que un compilador que realmente hace a su código (que es horrible, pero hermoso) y qué cómo una CPU realmente interpreta el código (igualmente), hay una solución bastante simple.

Considere estas instrucciones de texto:

Para ordenar bloques numerados:

1. recoger un bloque al azar.
2. si es el único bloque, deténgase.
3. mueve los bloques con números más bajos al lado izquierdo, números más altos a la derecha.
4. ordena los bloques de menor numeración.
5. ordena los bloques de mayor numeración.

Cuando llegue a las instrucciones 4 y 5, se le pedirá que inicie todo el proceso nuevamente. Sin embargo, esto no es un problema, porque todavía sabes cómo comenzar el proceso, y cuando todo termina, tienes un montón de bloques ordenados. Podría cubrir las instrucciones con trozos de papel y no serían más difíciles de seguir.

Answer 2

Trate de dibujar una ilustración usted mismo, eventualmente verá cómo funciona. Solo tenga en cuenta que cuando se realiza una llamada de función, primero obtendrá su valor return. Sencillo.

Answer 3

depuración tratar de utilizar relojes para conocer el estado de la variable

Answer 4

El truco es que la primera llamada a fibonacci() no regresa hasta que sus llamadas a fibonacci() han regresado.

Terminas con llamada tras llamada a fibonacci() en la pila, ninguna de las cuales regresa, hasta que llegas al caso base de n == 0 || n == 1. En este punto, la pila (potencialmente enorme) de llamadas de fibonacci() comienza a relajarse hacia la primera llamada.

Una vez que tenga su mente alrededor, es algo hermoso, hasta que su pila se desborde.

Answer 5

"¿Cómo puedes usar Fibonacci si aún no has terminado de explicar qué es?"

Esta es una forma interesante de cuestionar la recursividad. Aquí hay parte de una respuesta: Mientras define Fibonacci, no se ha definido pero, pero ha sido declarado. El compilador sabe que hay una cosa llamada Fibonacci, y que será una función de tipo int -> int y que se definirá cuando se ejecute el programa.

De hecho, así es como funcionan todos los identificadores en C, no solo los recursivos. El compilador determina qué cosas han sido declaradas, y luego pasa por el programa apuntando usos de esas cosas a donde realmente están las cosas (simplificación excesiva).

Answer 6

Comprender la recursión también requiere saber cómo funciona la pila de llamadas, es decir, cómo se llaman las funciones entre sí.
Si la función no tenía la condición para detenerse si n == 0 o n == 1, entonces la función se llamaría recursivamente para siempre. Funciona porque eventualmente, la función va a responder y devolver 1. En ese punto, el retorno de fibonacci (n-1) + fibonacci (n-2) también regresará con un valor, y la pila de llamadas se limpiará muy rápido

Answer 7

En el caso del código 2, aunque n alcanzará consiguiera un punto en el que es imposible satisfacer n> 0 y el método dejará de llamar misma recursivamente

para que se vea similares puede reemplazar la condición if (n == 0 || n == 1) con if (n < 2)

Además, no veo cómo la línea `Fibonacci de retorno (n-1) + Fibonacci (n-2) que funcionaría desde fibbonacci n-2 tiene que contener en cierto sentido de Fibonacci n-1 para trabajar, pero todavía no está allí.

sospecho que quería escribir: "desde fibbonacci n-1 tiene que contener en alguna de Fibonacci sentido n-2"
Si estoy en lo cierto, entonces verá desde el ejemplo de abajo, que en realidad de Fibonacci (n-2) se llamará dos veces para cada nivel de recursión (de Fibonacci (1) en el ejemplo):
1. al ejecutar de Fibonacci (n-2) en la actual el paso
2.al ejecutar de Fibonacci ((n-1) -1) en el siguiente paso

(También echa un vistazo más de cerca a la Spike's comment)

Supongamos que se llaman de Fibonacci (3), entonces call stack para fibonacci será así:
(Veer proporciona more detailed explanation)

 
n=3. fibonacci(3) 
n=3. fibonacci(2) // call to fibonacci(n-1) 
    n=2. fibonacci(1) // call to fibonacci(n-1) 
     n=1. returns 1 
    n=2. fibonacci(0) // call to fibonacci(n-2) 
     n=0. returns 1 
    n=2. add up, returns 2 
n=3. fibonacci(1) //call to fibonacci(n-2) 
    n=1. returns 1 
n=3. add up, returns 2 + 1 

Tenga en cuenta, que la adición en fibonacci (n) tiene lugar solo después de que regresan todas las funciones para args más pequeños (es decir, de Fibonacci (n-1), de Fibonacci (n-2) ... de Fibonacci (2), de Fibonacci (1), de Fibonacci (0))

Para ver lo que está pasando con call stack para números mayores podría ejecutar este código.

public static String doIndent(int tabCount){ 
    String one_tab = new String(" "); 
    String result = new String(""); 
    for(int i=0; i < tabCount; ++i) 
     result += one_tab; 
    return result; 
} 

public static int fibonacci(int n, int recursion_level) 
{ 
    String prefix = doIndent(recursion_level) + "n=" + n + ". "; 

    if (n == 0 || n == 1){ 
     System.out.println(prefix + "bottommost level, returning 1"); 
     return 1; 
    } 
    else{ 
     System.out.println(prefix + "left fibonacci(" + (n-1) + ")"); 
     int n_1 = fibonacci(n-1, recursion_level + 1); 

     System.out.println(prefix + "right fibonacci(" + (n-2) + ")"); 
     int n_2 = fibonacci(n-2, recursion_level + 1); 

     System.out.println(prefix + "returning " + (n_1 + n_2)); 
     return n_1 + n_2; 
    } 
} 

public static void main(String[] args) 
{ 
    fibonacci(5, 0); 
} 

Answer 8

Déjame recorrer la ejecución teniendo en cuenta n = 3. Espero eso ayude.

Cuando n = 3 => si la condición falla y demás ejecuta

return fibonacci (2) + fibonacci (1); 

Dividir la declaración:

1. encontrar el valor de Fibonacci (2)
2. encontrar el valor de Fibonacci (1)
   // Tenga en cuenta que no es fib (n-2) y no va a requerir fib (n-1) para su ejecución. Es independiente. Esto se aplica al paso 1 también.
3. añadir tanto los valores
4. retorno el valor resumió

La forma en que es ejecutado (Ampliación de los cuatro pasos anteriores):

1. encontrar el valor de Fibonacci (2)

   1. si falla, de lo contrario se ejecuta
   2. fibonacci (1)
      1. si ejecuta
      2. valor '1' vuelve al paso 1.2. y el control va al paso 1.3.
   3. de Fibonacci (0)
      1. si ejecuta valor
      2. '1' vuelve a la etapa 1.3. y el control va al paso 1.4.
   4. añadir tanto
      1. suma = 1 + 1 = 2 // de los pasos 1.2.2. y 1.3.2.
   5. retorno suma // valor '2' se devuelve al paso 1. y el control pasa a la etapa 2
      

2. encontrar el valor de Fibonacci (1)

   1. si ejecuta
   2. valor '1' se devuelve

3. Agregue ambos valores

   1. suma = 2 + 1 // desde los pasos 1.5. y 2.2.
4. devolver el valor resumió // suma = 3

Answer 9

voy a explicar lo que está haciendo su PC al ejecutar ese trozo de código con un ejemplo:

Imagine que está de pie en una habitación muy grande. En la habitación contigua a esta sala, tienes enormes cantidades de papel, bolígrafos y mesas. Ahora vamos a calcular fibonacci (3):

Tomamos una mesa y la colocamos en algún lugar de la habitación. Sobre la mesa colocamos un papel y escribimos "n = 3" en él. Entonces nos preguntamos "hmm, ¿3 es igual a 0 o 1?". La respuesta es no, así que haremos "return fibonacci (n-1) + fibonacci (n-2);".

Hay un problema, sin embargo, no tenemos idea de lo que "fibonacci (n-1)" y "fibonacci (n-2)" realmente hacen. Por lo tanto, tomamos dos tablas más y las colocamos a la izquierda y a la derecha de nuestra tabla original con un documento sobre las dos, diciendo "n = 2" y "n = 1".

Comenzamos con la tabla de la izquierda, y nos preguntamos "¿es 2 igual a 0 o 1?". Por supuesto, la respuesta es no, así que una vez más colocaremos dos tablas al lado de esta tabla, con "n = 1" y "n = 0" en ellas.

¿Siguen SIGUIENDO? Esto es lo que la habitación se parece a:

n = 1

n = 2 n = 3 n = 1

n = 0

Partimos de la mesa con "n = 1" , y bueno, 1 es igual a 1, ¡así que podemos devolver algo útil! Escribimos "1" en otro papel y volvemos a la tabla con "n = 2" en él. Colocamos el papel sobre la mesa e iremos a la otra mesa, porque aún no sabemos qué vamos a hacer con esa otra mesa.

"n = 0", por supuesto, devuelve 1 también, así que escribimos eso en un papel, regresemos a la tabla n = 2 y coloquemos el papel allí. En este punto, hay dos documentos en esta tabla con los valores de retorno de las tablas con "n = 1" y "n = 0" en ellos, por lo que podemos calcular que el resultado de esta llamada al método es en realidad 2, por lo que escríbalo en un papel y póngalo sobre la mesa con "n = 3" en él.

A continuación, vamos a la tabla con "n = 1" en todo el camino a la derecha, y podemos escribir inmediatamente 1 en un papel y ponerlo sobre la mesa con "n = 3" en él. Después de eso, por fin tenemos suficiente información para decir que Fibonacci (3) devuelve 3.

---

Es importante saber que el código que está escribiendo no es más que una receta. Todo lo que hace el compilador es transformar esa receta en otra receta que tu PC pueda entender. Si el código es completamente falso, como esto:

public static int NotUseful() 
    { 
     return NotUseful(); 
    } 

simplemente se bucle sin fin, o como en mi ejemplo, podrás seguir poniendo más y más tablas sin tener que llegar a ninguna parte útil. A su compilador no le importa lo que realmente hacen los fibonacci (n-1) o fibonacci (n-2).