números de fibonacci, ¿por qué funciona esta función recurrente?

Question

Estoy repasando un libro de programación y uno de los ejemplos es acerca de los números de Fibonacci, y cómo una función recurrente encuentra el número de Fibonacci para el enésimo.

El código es el siguiente:

Int fib (int n) 
{ 
If (n<3) 
Return (1); 
Else 
Return (fib(n-1))+(fib(n-2)) 
} 

Ahora bien, esto no es exacto, porque estoy escribiendo desde mi teléfono y tengo una comprensión de cómo el código está trabajando, se hace llamar hasta que vuelve 1, luego suma los valores de retorno hasta que tenga el número de Fibonacci correcto para la posición en la secuencia.

Así que no necesito ayuda con el código. Lo que sí necesito ayuda es entender por qué esto funciona. ¿Cómo da la respuesta correcta la suma de todas las devoluciones?

Por favor alguien puede explicar por qué esto está funcionando. Gracias. Me está volviendo loco.

Answer 1

Un número de Fibonacci se define como la suma de los dos números anteriores de Fibonacci. Eso le da lo siguiente:

1 1 2 3 5 8 13 ... 

Así que para la tercera serie (1 1) que tomaría el resultado de la búsqueda de la anterior - es decir, segundo (1 2) número y añadirlo a la serie antes del número anterior, es decir, 1er (1 2).

También debe comprender que el programa necesita calcular el valor de los dos números anteriores para poder calcular el número que desea saber. Por lo tanto, sigue llamándose a sí mismo, utilizando el mismo método, hasta que lo haya calculado todo.

Answer 2

Un número de fibonacci se define como la suma de los dos números de Fibonacci anteriores. Cada uno se define como la suma de los dos números anteriores de Fibonacci. Etcétera, etcétera, hasta llegar a 1. ¿Entender? Cualquier número aleatorio de Fibonacci se puede definir como la suma de dos números de Fibonacci; se pueden definir recursivamente como la suma de dos números de Fibonacci, etc. Es decir, la definición de un número de Fibonacci es fundamentalmente recursiva; es decir, la definición de eso implica lo que define.

Esto puede ser complicado, pero es muy fundamental para entender la recursividad y la informática. Sigue trabajando en eso; hará clic eventualmente.

Answer 3

Se llama recursion

Answer 4

sugeriría a entender cómo funciona la recursividad. Básicamente FIB función se ejecuta en sí con un argumento más pequeño hasta el argumento se reduce a 2, entonces, sólo se devuelve 1.

fib(1) = 1 
fib(2) = 1 
fib(3) = fib(2) + fib(1) = 1 + 1 = 2 
fib(4) = fib(3) [ fib(2) + fib(1) = 1 + 1 = 2 ] + fib(2) = 2 + 1 
... 

Una manera de entender cómo funciona es para ejecutarlo en un depurador paso a paso.

Answer 5

La recursividad es así:

1. Un niño no podía dormir, por lo que su madre le dijo una historia sobre una pequeña rana ,
2. que no podía dormir, así madre de la rana le dijo una historia acerca de un pequeño oso ,
3. que no podía dormir, por lo madre del oso le dijo una historia sobre una pequeña comadreja ...
4. que se durmió.
5. ..y el osito se durmió;
6. ... y la pequeña rana se durmió;
7. ... y el niño se durmió.

source

Answer 6

Por definición, los números de Fibonacci son la suma de los dos números anteriores en la serie (en la que los dos primeros son 0 y 1).

Por lo tanto, cuando obtiene el número de fibonacci en una ubicación, puede volver a escribirlo como la suma de los dos números anteriores de fibonacci.

Usando la recursividad, pasa por este proceso hasta que los "dos números de Fibonacci" sean previamente 1 y 1 (en el caso de este algoritmo), y luego continúe agregando los números juntos "respalde" la recursión hasta que vuelve a tu ubicación original en la secuencia.

Answer 7

Es la definición de números de Fibonacci.

n-th número de Fibonacci devuelve la suma de (n-1) th y (n-2) los números de Fibonacci.

Así que podemos demostrar, mediante el razonamiento inductivo, que si fib (n-1) y fib (n-2) dan el número de Fibonacci (n-1) y (n-2) -th válido, fib (n) = fib (n-1) + fib (n-2) será el n-ésimo número de Fibonacci válido.

El paso de base es que fib (1) y fib (2) son correctas (eso es todo FIB (1) = fib (2) = 1) ...

Answer 8

El truco para entender la recursividad es la comprensión de la apilar.

Estoy en la línea 2 en una función llamada main, todos mis variables locales se almacenan en mi marco de pila:

+------------------+ 
| main() variables | The stack frame 
+------------------+ 

entonces yo llamo fib(3), por lo que el equipo empuja mi posición actual (EIP) a la pila, luego crea un nuevo marco de pila para fib y lo agrega también. Sólo puedo siempre tener acceso al marco de pila superior:

+------------------+ 
| fib() n = 5  | Top of stack (current frame) 
+------------------+ 
| EIP: main @ 2,1 | 
+------------------+ 
| main() variables | Bottom of stack 
+------------------+ 

En la línea 4 de fib, llama fib de nuevo, por lo que la misma vuelva a suceder:

+------------------+ 
| fib() n = 4 | Top of stack 
+------------------+ 
| EIP: fib @ 4,1 | 
+------------------+ 
| fib() n = 5 | 
+------------------+ 
| EIP: main @ 2,1 | 
+------------------+ 
| main() variables | Bottom of stack 
+------------------+ 

y lo hace una y otra vez como el la función se llama recursivamente. La pila crece hasta que algo retorna, en cuyo punto, en la línea 2 de fib, devuelve 1.Esto hace aparecer el marco de la pila superior y la descarta, entonces regresa a la ejecución del puntero ejecución salvado y el programa continúa donde lo dejó

+------------------+ 
| fib() n = 3 | Top of stack 
+------------------+ 
    ... etc ... 
+------------------+ 
| EIP: main @ 2,1 | 
+------------------+ 
| main() variables | Bottom of stack 
+------------------+ 

Finalmente se termina de nuevo en la función que llama (o se obtiene un desbordamiento de pila ya que crece demasiado grande). La clave para recordar es que cada vez que se llama a la función, obtiene un nuevo marco de pila que contiene todas las variables locales, y se guarda su posición anterior. Eso es recursividad.

El principal problema es que al enseñar a la gente a recursividad, todos siempre usan la secuencia de Fibonacci, lo que significa que tienen dos llamadas a funciones recursivas en una línea. Esto es innecesariamente confuso, ¡estoy seguro de que estarás de acuerdo!

Answer 9

Este video tutorial le debe dar una mejor idea de cómo funciona la recursividad de Fibonacci

[link] http://www.schooltrainer.com/study-material/computer-science/stepping-through-recursive-fibonacci-function.html