Fibonacci naïf et l'explosion de l'arbre d'appels

La suite de Fibonacci se définit simplement : fib(0)=0, fib(1)=1, et pour n≥2, fib(n)=fib(n-1)+fib(n-2). La traduction directe en fonction récursive semble naturelle :

def fib_naif(n):
    if n <= 1:
        return n
    return fib_naif(n - 1) + fib_naif(n - 2)

Ce code est correct, mais catastrophiquement lent. Pourquoi ? Parce que pour calculer fib(n), la fonction appelle fib(n-1) ET fib(n-2), qui eux-mêmes rappellent des sous-parties déjà calculées ailleurs dans l'arbre. Regarde l'arbre d'appels complet de fib(5) :

fib(5)
  fib(4)
    fib(3)
      fib(2)
        fib(1)
        fib(0)
      fib(1)
    fib(2)
      fib(1)
      fib(0)
  fib(3)                (recalcule tout ce sous-arbre, deja fait plus haut !)
    fib(2)
      fib(1)
      fib(0)
    fib(1)

Pour ce petit exemple avec n=5, cela représente déjà 15 appels de fonction, alors qu'il n'existe que 6 valeurs distinctes (fib(0) à fib(5)) à calculer. Le nœud fib(3) est recalculé entièrement deux fois, fib(2) trois fois, fib(1) cinq fois : à chaque niveau, le nombre d'appels redondants augmente.

En réalité, le nombre total d'appels de fib_naif(n) croît de façon exponentielle avec n (proche de 1.618^n, le nombre d'or). Pour n=40, cela représente des centaines de millions d'appels : le programme devient inutilisable en pratique, alors que le calcul « à la main » ne nécessite que 40 additions si on s'y prend intelligemment.

Le problème n'est donc pas la formule mathématique, qui est juste, mais la façon dont on la calcule : on refait sans cesse le même travail parce qu'on ne garde aucune trace des résultats déjà obtenus.