Ineficiencia de Fibonacci Recursivo

Aquí daré una breve pero acertada explicación de por qué usar la función de Fibonacci en términos recursivos es a la larga bastante ineficiente. Veamos su definición es tales términos:

fib(1)=1
fib(2)=1
fib(n)=fib(n-1)+fib(n-2)     cuando n>2

Ahora pongamos como ejemplo que queremos sacar Fibonacci 6, o sea n=6. Primero debemos tener en cuenta que como n=6 no es un caso base, se vuelve a invocar recursivamente dos veces, primer con n=5 y luego con n=4. Éstos números a su ves necesitan dos llamadas mas, y cada una de estas harán otras dos llamadas, y así sucesivamente hasta llegar a los números base que no necesitan una llamada, y cortan la cadena de llamadas recursivas.

Aquí se representan las llamadas gráficamente, en donde el resultado es una estructura de árbol binario, en donde la profundidad depende del n inicial. 

Podemos ver en la gráfica que cada círculo representa un valor de n para la invocación de una función, empezando con n=6. Para calcular fib(6), es necesario calcular fib(5) y fib(4), y para calcular fib(4) es necesario calcular fib(3) y fib(2), y así sucesivamente, hasta llegar a fib(1) y fib(2), que son los casos base y donde la recursividad se corta. No parece mucho, pero imaginen si queremos encontrar fib(25), tendríamos que dibujar 150000 nodos!

Otra cosa importante a notar es que por la propia implementación recursiva de la función algunos valores se calculan más veces de lo necesario, por ejemplo fib(4) se calcula dos veces y fib(3) se calcula tres veces, cuando sólo se ocupan calcular una ves. Calcular un valor grande como fib(50) tardaría bastante tiempo en realizarse, tanto que cerraríamos el programa en desesperación! Es por esto que se concluye que para sacar números Fibonacci de una manera eficiente es mejor hacerlo de una manera iterativa, que tomaría exponencialmente menos tiempo que de manera recursiva. 

Referencias:

http://latecladeescape.com/basico/entender-la-recursividad.html