Pistas

Si estuvo jugando con la función fibonacci, es posible que haya notado que cuanto más grande es el argumento que le da, más tiempo le cuesta ejecutarse. Más aún, el tiempo de ejecución aumenta muy rápidamente. En nuestra máquina, fibonacci(20) acaba instantáneamente, fibonacci(30) tarda más o menos un segundo, y fibonacci(40) tarda una eternidad.

Para entender el por qué, observe este gráfico de llamadas de fibonacci con
n=4:

Un gráfico de llamadas muestra un conjunto de cajas de función con lı́neas que conectan cada caja con las cajas de las funciones a las que llama. En lo alto del gráfico, fibonacci con n=4 llama a fibonacci con n=3 y n=2. A su vez, fibonacci con n=3 llama a fibonacci con n=2 y n=1. Y ası́ sucesivamente.

Cuente cuántas veces se llama a fibonacci(0) y fibonacci(1). Es una solución ineficaz al problema, y empeora mucho tal como crece el argumento.

Una buena solución es llevar un registro de los valores que ya se han calculado almacenándolos en un diccionario. A un valor que ya ha sido calculado y almacenado para un uso posterior se le llama pista. Aquí hay una implementación de fibonacci con pistas:

El diccionario llamado anteriores mantiene un registro de los valores de Fibonacci que ya conocemos. El programa comienza con sólo dos pares: 0 corresponde a 1 y 1 corresponde a 1.

Siempre que se llama a fibonacci comprueba si el diccionario contiene el resultado ya calculado. Si está ahı́, la función puede devolver el valor inmediatamente sin hacer más llamadas recursivas. Si no, tiene que calcular el nuevo valor. El nuevo valor se añade al diccionario antes de que la función vuelva.

Con esta versión de fibonacci, nuestra máquina puede calcular fibonacci(40)
en un abrir y cerrar de ojos.