La suite de Fibonnaci

Prenons l'exemple de la fonction qui calcule les nombres de la suite de Fibonnaci.

Cette fonction récursive est un candidat idéal pour la Memoization. En effet, calculer fib( 5 ) fera appel à fib( 4 ) et fib( 3 ). fib( 4 ) fera appel à fib( 3 ) et fib( 2 ) et ainsi de suite. Graphiquement, les appels récursif à fib( x) peuvent être représentés comme un arbre :

Dans cet exemple, il faudrait calculer 1 fois fib(4), deux fois fib(3), trois fois fib(2) et 2 fois fib(1). La situation serait bien pire pour le calcul de fib(25) : 1 fois fib(24), 2 fois fib(23), ..., 28657 fois fib(3), 46638 fois fib(2) et 28657 fois fib(1).

Bref, cela représente un nombre énorme de calculs et, donc, de temps et d'espace. En fait, la complexité temporelle T_fib(n) = O(fib(n)). Mémoriser les différents résultats permettra de ne calculer qu'une seule fois les valeurs de fib( x ) pour chaque valeur de x.