Dev - C++ - C++ Relación con la Sucesion Fibonacci

Hola,
Me encontraba leyendo sobre la recursión en las funciones y pues me puse a practicar, ya que me encuentro aprendiendo C++ utilizo el dev-cpp, en fin me puse a practicar y logre hacer mi programa con mi concepto básico de lo que era la sucesión fibonacci, en fin... El hecho es que al seguir leyendo me encuentro con la sucesión pero esta terminaba con:

return ( fib(n-1)+fib(n-2) )

Mientras que a mi me habia quedado asi:


Para no hacer larga la historia, quede perdido por un instante ya que logicamente para encontrar la posición 5 por ejemplo (5-1)+(5-2)=7 mientras que no me daba ese resultado... luego de un rato segui buscando y encontre, que era la formula para saber el valor de esa posicion y segun el texto que encontre la sucesion empieza con [0,1].

Por tanto (5-1)=4. La posición 4 tiene el valor "2". Entonces (5-2)=3. La posición 3 es "1". Es decir que el ejemplo anterior (5-1)+(5-2)=3.

[0,1,1,2,3,5,8] Si se fijan la posición quinta es el 3 entonces estaría correcto. Bueno ya di muchas vueltas pero mi duda finalmente es, porque C++ entiende esto? Me podria dar problemas o como puedo evitarlo, ya que no es muy logico si se trata de otra operación.

La sucesión de Fibonacci consiste en que cada término de la sucesión es la suma de los dos anteriores. La sucesión se define:

Fib(0) = 0
Fib(1) = 1

y a partir de aquí:

Fib(n) = Fib(n-1) + Fib(n-2)

es decir, se trata de una función recursiva (se llama a sí misma).

En tal caso,

Fib(5) = Fib(5-1) + Fib(5-2) = Fib(4) + Fib(3) = 3+2 = 5

Ten en cuenta que el primer elemento corresponde a Fib(0), que vale 0, no a Fib(1).

Dado que es una función recursiva, hay que tener muy clara la condición de retorno (si la implementas de manera recursiva). Por ejemplo:

Si utilizas esta función recursiva a partir de la definición, verás que el tiempo de ejecución empieza a ser notorio con cantidades no muy elevadas (a partir de 35-40). Este problema se da con frecuencia en el empleo de funciones recursivas.

En cambio, con la versión no recursiva, por ejemplo,


la respuesta es casi instantánea. Como puedes ver, la primera solución es mucho más intuitiva y elegante, aunque a costa de la velocidad de ejecución para valores altos.

Por cierto, que estas funciones funcionan correctamente hasta el término número 46 inclusive (47 con tipo unsigned). A partir de aquí, con enteros de 32 bits, ya tenemos problemas de desbordamiento y empiezan a aparecer soluciones sin sentido. Si necesitas ir más allá, tendrás que utilizar enteros de 64 bits (si tu compilador dispone de ellos), o pasar a tipos float o double.

Gracias por la respuesta!

Ahora estoy empezando a leer un poco más sobre las funciones recursivas, veo que estaba en un error y me deje llevar.

Y tienes razón, el primer codigo usando la función recursiva se puede ver más entendible y elegante, aunque a costa de recursos, de nuevo gracias por tu respuesta, me sirve de mucho. Saludos!