Site WWW de Laurent Bloch
Slogan du site

ISSN 2271-3905
Cliquez ici si vous voulez visiter mon autre site, orienté vers des sujets moins techniques.

Pour recevoir (au plus une fois par semaine) les nouveautés de ce site, indiquez ici votre adresse électronique :

Analyse de l’algorithme de Fibonacci
Article mis en ligne le 22 mars 2006
dernière modification le 13 décembre 2022

par Laurent Bloch

Processus récursif en arbre : Fibonacci

Léonard de Pise, dit Fibonacci, a joué un rôle important dans l’histoire des mathématiques, notamment en introduisant en Europe les résultats élaborés par les mathématiciens arabes qu’il fréquentait quand son père était ambassadeur de la République de Pise à Bejaïa. Il a décrit l’algorithme qui porte son nom (et qui est réputé modéliser la descendance d’un couple de lapins et le pavage des sentiers dans les résidences secondaires) en 1202.

Les nombres de Fibonacci sont définis ainsi :

 F0 = 0
 F1 = 1
 Fn = Fn-1 + Fn-2 autrement.

Le programme récursif s’en déduit aussi aisément que celui de la factorielle :

  1. (define (fib n)
  2.    (if (< n 2)
  3.       n
  4.       (+ (fib (- n 1))
  5.          (fib (- n 2)))))

Télécharger

Notre procédure comporte deux appels récursifs. Chaque appel à fib, hors le cas de base, engendre deux appels à fib. Représentons le cas de (fib 4) par l’arbre de la figure 1.

Figure 1 : Récursion en arbre pour Fibonacci.

Nous voyons que notre algorithme n’est guère efficace, il calcule deux fois (fib 2), trois fois (fib 1), deux fois (fib 0). Que serait-ce pour une valeur plus grande de n... En fait, si l’on appelle Li,n le nombre de fois où l’on calcule Fi au cours du calcul de Fn par notre algorithme, on peut montrer par induction que :
L1,n + L0,n = Fn + 1
soit le nombre de feuilles de l’arbre. En effet :

 c’est vrai pour n=2 : L1,2= 1, L0,2 = 1, leur somme vaut 2 soit F3 ;
 c’est vrai pour n=3 : L1,3= 2, L0,3 = 1, leur somme vaut 3 soit F4 ;
 si c’est vrai pour n−2 et n−1, qu’en est-il pour n : comme Fn se construit en additionnant Fn−1 et Fn−2 et que notre algorithme parcourt froidement leurs arbres d’évaluation sans faire aucune économie sur les calculs redondants, l’arbre de Fn a autant de feuilles de chaque sorte que les deux arbres de Fn−1 et de Fn−2 réunis, et nous avons :

L1,n = L1,n−1 + L1,n−2

L0,n = L0,n−1 + L0,n−2

d’où :

L1,n + L0,n = (L1,n−1 + L0,n−1) + (L1,n−2 + L0,n−2)

soit par hypothèse :

L1,n + L0,n = Fn + Fn−1

or par définition de F :

L1,n + L0,n = Fn+1

Nous reviendrons sur cet algorithme à la section 2.2 pour étudier plus en détail son fonctionnement.

Pouvons-nous trouver un algorithme plus efficace, c’est-à-dire à la récursivité moins foisonnante ? Oui, par exemple celui qui figure ci-dessous.

  1. (define (fib n)
  2.    (let boucle ((a 1)
  3.                 (b 0)
  4.                 (compteur n))
  5.       (if (zero? compteur)
  6.           b
  7.           (boucle (+ a b)
  8.                   a
  9.                   (- compteur 1)))))

Télécharger

Cet algorithme itératif est similaire à celui proposé pour la factorielle, à ceci près qu’il doit conserver en mémoire les résultats des deux itérations précédentes. Comme pour la factorielle, le procédé retenu pour organiser la persistance de ces deux valeurs repose sur leur passage en arguments d’appel en appel. C’est simple et élégant, sinon efficace.

Analyse de performance : Fibonacci

Essayons avec la commande Unix time une approche expérimentale naïve dont les résultats sont donnés dans le tableau ci-dessous.

En espérant ne pas être victime d’un artefact, nous observons que tant Fn que le temps mis à le calculer tn croissent vite, pas au point de doubler à chaque itération, mais en faisant plus que doubler toutes les deux itérations. Cette observation suggère que Fn et tn ont une croissance exponentielle comparable à celle d’une fonction de valeur kn, avec √2 < k < 2. Si k valait √2, Fn doublerait toutes les deux itérations, si k valait 2, Fn doublerait à chaque itération.

n Fn temps de calcul tn
25 75 025 0,210s
26 121 393 0,290s
27 196 418 0,410s
28 317 811 0,610s
29 514 229 0,940s
30 832 040 1,440s
31 1 346 269 2,300s
32 2 178 309 3,700s
33 3 524 578 5,910s
34 5 702 887 9,510s
35 9 227 465 15,330s
36 14 930 352 24,800s

Cette observation empirique ne saurait nous convaincre du résultat, elle n’est que la suggestion d’une voie à explorer pour le trouver en raisonnant sur notre algorithme.

De la définition nous pouvons déduire sans difficulté que pour tout n > 2, Fn est positif et supérieur à Fn−1. Plus précisément, Fn = Fn−1 + Fn−2 or pour tout n > 3 :

Fn > Fn−1 > Fn−2

donc :

2 Fn−1 > Fn > 2 Fn−2

ce qui confirme notre observation.

Reste à montrer que le temps de calcul tn de notre algorithme récursif croît comme Fn lui-même. L’examen de l’arbre d’évaluation du programme nous apprend que tout son travail se résume en fait à additionner des 1 et des 0. Toutes les branches de l’arbre aboutissent à des feuilles de contenus F1 ou F0 qui valent 1 ou 0. En d’autres termes le cas de base de la récursion fournit les 1 et les 0 qui sont aux feuilles et le reste de la procédure fait les additions qui sont aux nœuds intérieurs (qui ne sont pas des feuilles).

Nous avons calculé ci-dessus le nombre de feuilles de l’arbre pour calculer Fn : Fn+1 feuilles contenant des 0 ou des 1. Imaginons tous ces 0 et ces 1 du cas de base empilés, et que nous répétions l’opération suivante :

 retirer de la pile les deux nombres du dessus de la pile ;
 les additionner ;
 replacer le résultat au sommet de la pile ;

jusqu’à ce qu’il n’y ait plus dans la pile qu’un seul nombre, qui serait d’ailleurs le résultat cherché Fn, combien aurions-nous fait d’additions ? Ou, ce qui revient au même, combien notre arbre a-t-il de nœuds intérieurs ?

Chaque addition réduit de 1 le nombre de nombres dans la pile, parce que nous en retirons deux nombres et que nous en remettons un. Au départ il y avait Fn+1 nombres, d’après notre calcul ci-dessus, à la fin il n’y en a plus qu’un, le résultat Fn. Le nombre de nombres a diminué de Fn+1 − 1, c’est le nombre d’additions effectué. Le nombre d’appels à la fonction fib est égal à la somme de ce nombre d’additions et du nombre de feuilles de l’arbre correspondant au cas de base, soit 2 Fn+1 − 1 appels à fib. Bref, le calcul de F30 effectue 2 692 537 appels à fib dont 1 346 269 correspondent au cas de base et 1 346 268 sont des additions.

Pour mieux nous convaincre de ce résultat nous pouvons démontrer par induction que le nombre d’additions pour calculer Fn est égal à Fn+1 − 1 :

 c’est vrai pour n=2 : il nous faut une addition, soit F3 − 1 ;
 pour n=3 il faut deux additions, soit F4 − 1 ;
 si le calcul de Fn−1 effectue Fn − 1 additions et si le calcul de Fn−2 en effectue Fn−1 − 1, combien en effectue le calcul de Fn ? Appelons An le nombre d’additions nécessaires au calcul de Fn. Notre algorithme calcule Fn tout simplement en recalculant indépendamment Fn−1 et Fn−2 et en additionnant les résultats, soit :

An = An−1 + An−2 + 1

= (Fn − 1) + (Fn−1 − 1) + 1

= Fn + Fn−1 −1

soit par définition de F :

= Fn+1 − 1

Nous sommes maintenant convaincus que la fonction de Fibonacci et le temps nécessaire à la calculer par notre algorithme récursif ont une croissance exponentielle de la forme kn, où n est le rang du nombre de Fibonacci et k un nombre réel plus grand que √2 et plus petit que 2.

Il serait possible de calculer k avec une plus grande précision, c’est d’ailleurs un nombre très intéressant au sujet duquel Cormen et ses collègues ainsi que D. Knuth et les siens nous donneront des aperçus passionnants. Mais tel n’est pas notre propos ici. Nous voulons juste trouver un moyen de calculer un ordre de grandeur du temps d’exécution de notre algorithme selon la valeur de n. Si cet ordre de grandeur est de plus un majorant du temps de calcul nous pourrons avec sûreté prévoir la possibilité d’achever notre calcul.

Amélioration de Fibonacci : memoization

Une idée séduisante est la suivante : prenons notre programme fib tel qu’il est et associons-lui une table dans laquelle seront archivés les valeurs de F déjà calculées. La taille de la table est facile à prévoir : pour calculer Fn il faut une table de n cases.

À chaque calcul de Fi nous consultons la iième case de la table, soit le calcul a déjà été effectué et nous y recueillons le résultat, soit nous le calculons et l’y inscrivons pour un usage ultérieur.

Cette méthode est élégante, efficace et indépendante de l’algorithme utilisé. En voici une réalisation, due à Abelson et Sussman :

  1. (define (make-table)
  2.   (list '*TABLE*))
  3.  
  4. (define (cherche clef table)
  5.   (let ((result (assoc clef (cdr table))))
  6.     (if result
  7.         (cdr result)
  8.         #f)))
  9.  
  10. (define (insert! clef valeur table)
  11.   (let ((result (assoc clef (cdr table))))
  12.     (if result
  13.         (set-cdr! result valeur)
  14.         (set-cdr! table
  15.                   (cons (cons clef valeur)
  16.                   (cdr table)))))
  17.   'ok)

Télécharger

et son application à notre programme fib :

  1. (define (memoize f)
  2.   (let ((table (make-table)))
  3.     (lambda (x)
  4.       (let ((result-deja-obtenu
  5.                (cherche x table)))
  6.         (or result-deja-obtenu
  7.             (let ((result (f x)))
  8.               (insert! x result table)
  9.               result))))))
  10.  
  11. (define memo-fib
  12.   (memoize (lambda (n)
  13.              (cond ((= n 0) 0)
  14.                    ((= n 1) 1)
  15.                    (else (+ (memo-fib (- n 1))
  16.                             (memo-fib (- n 2))))))))

Télécharger

Pour compiler cela avec Bigloo, ajouter en tête :

  1. (module memofib
  2.    (main get-n))
  3.  
  4. (define (get-n args)
  5.    (print (memo-fib (string->number (cadr args)))))

Télécharger

Memoization dans un vecteur

Voici une variante de cet algorithme de memoization, qui, au lieu de mémoizer les valeurs déjà calculées dans une liste d’associations, utilise pour cela un vecteur. L’avantage est que l’accès à la valeur se fait en temps constant et plus vite, les limites de cette solution sont que (sous cette forme tout au moins) elle ne s’applique qu’aux recherches sur une clé qui prenne des valeurs entières positives, et que la taille du vecteur doit être fixée au départ, ce qui limite la valeur de la clé. Voici les procédures de gestion de la table de memoization :

  1. (define (make-table n)
  2.    (vector
  3.     "*TABLE*"
  4.     (make-vector n #f)))
  5.  
  6. (define (cherche clef table)
  7.    (vector-ref (vector-ref table 1) clef))
  8.  
  9. (define (insert! clef valeur table)
  10.    (vector-set!
  11.     (vector-ref table 1) clef valeur))

Télécharger

et les procédures de calcul proprement dites :

  1. (define (memoize f)
  2.    (let ((table (make-table 60)))
  3.       (lambda (x)
  4.          (let ((result-deja-obtenu
  5.                 (cherche x table)))
  6.             (or result-deja-obtenu
  7.                 (let ((result (f x)))
  8.                    (insert! x result table)
  9.                    result))))))
  10.  
  11. (define fib
  12.    (memoize
  13.     (lambda (n)
  14.        (if (< n 2)
  15.            n
  16.           (+ (fib (- n 1))
  17.              (fib (- n 2)))))))

Télécharger

Le texte à ajouter pour compiler avec Bigloo est
le même.