Ejemplo para calcular la función de Fibonacci

Recordemos que la fórmula para calcular la sucesión de Fibonacci es:


{{a}_{n+1}}={{a}_{n-1}}+~{{a}_{n,~n\ge 1}}

Calcular los 10 primeros términos de la sucesión de Fibonacci:


Los 6 primeros términos ya los hemos calculado:


{{a}_{0}}=0

{{a}_{1}}=1

{{a}_{2}}=1

{{a}_{3}}=2

{{a}_{4}}=3

{{a}_{5}}=5


El séptimo término es:

{{a}_{6}}=~{{a}_{4+~}}{{a}_{5}}=3+5=8

El octavo término es:


{{a}_{7}}=~{{a}_{5+~}}{{a}_{6}}=5+8=13

El noveno término es:


{{a}_{8}}=~{{a}_{6+~}}{{a}_{7}}=8+13=21

El décimo término es:


{{a}_{97}}=~{{a}_{7+~}}{{a}_{68}}=13+21~=34

Al resolver la función de Fibonacci por programación dinámica corresponderá a una función que es bien conocida:


f\left( x \right)=f\left( x-1 \right)+f\left( x-2 \right)

Árbol de la sucesión de Fibonacci. Adaptación del libro Investigación de operaciones de Harold Kuhn.

(Para ampliar la imagen haga clic sobre ella)

En programación una forma óptima de resolverlo es no volver a calcular, ya que esta lleva a tiempo computacional, por lo tanto, si pudiéramos calcular una sola vez, por ejemplo, para f1 nos evitaríamos dos operaciones.