La fonction de Fibonacci
Rappelons que la suite de Fibonacci (fn)n≥0 est définie par :
\(f_{0} = f_{1} = 1\),
\(f_{n+2} = f_{n} + f_{n+1}\).
Ce que l'on peut traduire par :
int fibo(int n){
if(n<=1) return 1 ;
else return(fibo(n-2)+fibo(n-1)) ;
}
La complexité de cette fonction est exponentielle. Peut-on réduire celle-ci ?
La simple vue de la fonction nous fait comprendre que des calculs se répètent.
La définition est : fn+2 = fn + fn+1. En substituant fn+1 par l'expression qui a permis de la calculer, on obtient : fn+2= fn + fn-1 + fn.
On voit que le calcul de fn sera fait au moins 2 fois pour calculer fn+2, mais également 4 fois pour calculer fn+3, etc.
Pour éviter de répéter les calculs, nous pouvons stocker les valeurs des éléments déjà calculés dans un tableau.