recursivo - recursion java

¿Cómo funciona la función recursiva de fibonacci "funcionar"?

Question

Soy nuevo en Javascript y estaba leyendo sobre ello, cuando llegué a un capítulo que describía la función recursiva. Utilizó una función de ejemplo para encontrar el enésimo número de la secuencia de Fibonacci. El código es el siguiente:

function fibonacci(n) {
if (n < 2){
return 1;
}else{
return fibonacci(n-2) + fibonacci(n-1);
}
}
console.log(fibonacci(7));
//Returns 21

Tengo problemas para entender exactamente qué está haciendo esta función. ¿Alguien puede explicar lo que está pasando aquí? Me estoy quedando atrapado en la 5ª línea, donde la función se llama a sí misma. ¿Que esta pasando aqui?

Answer 1

Aquí hay muchas buenas respuestas, pero hice este diagrama que ayuda a explicar mejor el resultado de la función. Los únicos valores que se devolverán alguna vez son 1 o 0 (su ejemplo devuelve 1 para n <2, pero en su lugar debe devolver n).

Esto significa que cada llamada recursiva eventualmente terminará devolviendo un 0 o 1. Estas terminan siendo "almacenadas en caché" en la pila y "llevadas" a la invocación original y agregadas juntas.

Entonces, si dibujara este mismo diagrama para cada valor de ''n'', podría encontrar la respuesta manualmente.

Este diagrama ilustra aproximadamente cómo se devuelve cada función para fib (5).

Esto muestra el flujo de control, es decir, el orden de ejecución de las funciones. Recuerde que el código siempre se ejecuta a la izquierda-> derecha y arriba-> abajo. Por lo tanto, cada vez que se llama a una nueva función, se pausa y luego se produce la siguiente invocación.

Lo siguiente ilustra el flujo de control real basado en su publicación original. Tenga en cuenta que la condición base es if (n <= 0) {return 0} else if (n <= 2) {return 1;} para simplificar:

1. fib(5) {
return fib(4) + fib(3);
2. fib(4) {
return fib(3) + fib(2);
3. fib(3) {
return fib(2) + fib(1);
4. fib(2) {
A= return 1;
};
5. fib(1) {
B= return 1;
};
C= return 2; // (1 + 1)
};
6. fib(2) {
D= return 1;
};
E= return 3; // (2 + 1)
};
7. fib(3) {
return fib(2) + fib(1);
8. fib(2) {
F= return 1;
};
9. fib(1) {
G= return 1;
};
H= return 2; // (1 + 1)
};
I= return 5; // (3 + 2)
};

Answer 2

Creo que estas dos funciones me dieron una explicación mucho más clara de la recursividad (de esta publicación del blog ):

function fibDriver(n) {
return n === 0 ? 0 : fib(0, 1, n);
}
function fib(a, b, n) {
return n === 1 ? b : fib(b, a + b, n-1);
}

Answer 3

Espero que lo siguiente ayude. Vocación:

fibonacci(3)

Llegará a la línea 5 y lo hará:

return fibonacci(1) + fibonacci(2);

la primera expresión llama a la función nuevamente y devuelve 1 (ya que n < 2 ).

El segundo llama a la función nuevamente, llega a la 5ª línea y lo hace:

return fibonacci(0) + fibonacci(1);

Ambas expresiones devuelven 1 (ya que n < 2 para ambas), por lo que esta llamada a la función devuelve 2.

Entonces la respuesta es 1 + 2, que es 3.

Answer 4

Estás definiendo una función en términos de sí mismo. En general, fibonnaci(n) = fibonnaci(n - 2) + fibonnaci(n - 1) . Simplemente estamos representando esta relación en código. Entonces, para fibonnaci(7) podemos observar:

• fibonacci(7) es igual a fibonacci(6) + fibonacci(5)
• fibonacci(6) es igual a fibonacci(5) + fibonacci(4)
• fibonacci(5) es igual a fibonacci(4) + fibonacci(3)
• fibonacci(4) es igual a fibonacci(3) + fibonacci(2)
• fibonacci(3) es igual a fibonacci(2) + fibonacci(1)
• fibonacci(2) es igual a fibonacci(1) + fibonacci(0)
• fibonacci(1) es igual a 1
• fibonacci(0) es igual a 1

Ahora tenemos todas las piezas necesarias para evaluar fibonacci(7) , que era nuestro objetivo original. Observe que el caso base - return 1 cuando n < 2 - es lo que hace esto posible. Esto es lo que detiene la recursión, de modo que podemos comenzar el proceso de desenrollar la pila y sumar los valores que estamos devolviendo en cada paso. Sin este paso, seguiríamos llamando a fibonacci en valores cada vez más pequeños hasta que el programa finalmente se bloquee.

Podría ayudar agregar algunas declaraciones de registro que ilustran esto:

function fibonacci(n, c) {
var indent = "";
for (var i = 0; i < c; i++) {
indent += " ";
}
console.log(indent + "fibonacci(" + n + ")");
if (n < 2) {
return 1;
} else {
return fibonacci(n - 2, c + 4) + fibonacci(n - 1, c + 4);
}
}
console.log(fibonacci(7, 0));

Salida:

fibonacci(7)
fibonacci(5)
fibonacci(3)
fibonacci(1)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(4)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(3)
fibonacci(1)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(6)
fibonacci(4)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(3)
fibonacci(1)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(5)
fibonacci(3)
fibonacci(1)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(4)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(3)
fibonacci(1)
fibonacci(2)
fibonacci(0)
fibonacci(1)

Los valores en el mismo nivel de sangría se suman para producir el resultado para el nivel anterior de sangría.

Answer 5

Para calcular el nésimo número de Fibonacci, la relación es F (n) = F (n-2) + F (n-1).

Si implementamos la relación en el código, para el enésimo número, calculamos el (n-2) th y (n-1) número th usando el mismo método.

Cada número subsiguiente es la suma de los dos números anteriores. Por lo tanto, el séptimo número es la suma de los números sexto y quinto. De manera más general, el n-ésimo número es la suma de n-2 y n-1, siempre que n> 2. Como las funciones recursivas necesitan una condición de detención para detener el recursivo, aquí n <2 es la condición.

f (7) = F (6) + F (5);

a su vez, F (6) = F (5) + F (4)

F (5) = F (4) + F (3) ... continúa hasta n <2

F (1) devuelve 1

Answer 6

Paso 1) Cuando se llama a fibonacci(7) imagine lo siguiente (observe cómo cambié todas las n a 7):

function fibonacci(7) {
if (7 < 2){
return 1;
}else{
return fibonacci(7-2) + fibonacci(7-1);
}
}

Paso 2) Dado que (7 < 2) es obviamente falso, vamos a fibonacci(7-2) + fibonacci(7-1); que se traduce en fibonacci(5) + fibonacci(6); Como fibonacci(5) es lo primero, se llama (esta vez cambia la n a 5):

function fibonacci(5) {
if (5 < 2){
return 1;
}else{
return fibonacci(5-2) + fibonacci(5-1);
}
}

Paso 3) Y o por supuesto, también se llama a fibonacci(6) , por lo que lo que sucedió es que para todos se llama fibonacci . Se llama a 2 nuevos fibonacci .

Visualización:

 fibonacci(7)
____|_____
| |
fibonacci(5) fibonacci(6)
____|____ ____|_____
| | | |
fib(3) fib(4) fib(4) fib(5)

¿Ves cómo se ramifica? cuando va a parar? Cuando n convierte en menos de 2, es por eso que tiene if (n < 2) . En ese punto, la ramificación se detiene y todo se suma.

Answer 7

La función se está llamando a sí misma. Esa es simplemente la definición de una función recursiva. En la 5ª línea, se transfiere la ejecución a sí mismo al pasar parámetros que darán como resultado un valor.

Para garantizar que una función recursiva no se convierta en un bucle sin fin, debe haber algún tipo de condición que no se llame a sí misma. El objetivo de su código en la pregunta es realizar los cálculos de una secuencia de fibonacci.

Answer 8

/* * Steps Fibonacci recursion * 1) 3 gets passed. (3 is printed to the screen during this call) * 2) Fibonacci A gets decrements by 2 and recursion happens passing 1 as a param. (1 is printed to the screen during this call) * 3) Fibonacci A hits the base case returning 1 and it "unwinds". (No recursion here) * 4) Fibonacci B gets called, decrementing the previous value of n (3 was the previous value of n before A made the returning call) to 2. (2 is printed to the screen during this call) * 5) Fibonacci A is called again subtracting 2 from n (2-2=0) and passes 0 as a param. (1 is printed to the screen during this call since it''s converted from 0) * 6) Fibonacci A hits the base case and "unwinds" (no recursion here) * 7) Fibonacci B is called subtracting 1 from 2 (2 was the previous value of n before A made the returning call) and passes 1 as a param. (1 is printed to the screen during this call) * 7) Fibonacci B now hits the base case, returning 1 and "unwinds" (no recursion here) * 8) Fibonacci B retraces it''s steps back through All previous fucntion calls and values of n (n=2 in our case) and adds [them] to the copy of n=1 stored in its local scope * 9) Once Fibonacci B completes the "unwinding" process, it returns the calculated value to the original caller (no recursion here) Note* Each instance of Fibonacci recursion creates its own scope and stores the returned value in a copy of n (in our case 1). As it the function "unwinds" it executes subsequent code that receive the value of n at that time. (all functions that call other functions "unwind" back through previous calls once they return) In the last call of our Fibonacci example, Fibonacci B receives the value of n=2 as Fibonaccci A "unwinds" since that was the last value before it made the returning call. Once Fibonacci B reached the base case and "unwound", it retraced its steps back through all previous values of n (in our case just n=2) and added [them] to its local copy of n=1. * The result when passing the number 3 is: 3 1 2 1 1 (3) */

var div = document.getElementById(''fib'');
function fib( n, c ) {
var indent = "";
for (var i = 0; i < c; i++) {
indent += " ";
}
var v = n===0 ? 1 : n
var el = document.createElement(''div''),
text = indent + "fibonacci(" + v + ")";
el.innerHTML = text;
div.appendChild(el);
if(n<2){
return 1;
}
return fib(n-2, c + 4) + fib(n-1, c + 4);

}