Fibonacci de 40 : plus de 300 millions d'appels
Calculer fib(40) naïvement demande plus de 331 millions d'appels, soit plusieurs secondes.
Par Jimenez Julien, éditeur de Calepin Binaire · mis à jour le
- Valeur de F(40)
- 102 334 155
- Appels de la version récursive naïve
- 331 160 281
- Appels avec mémorisation
- 79
- Additions de la version itérative
- 39
- Durée de la version naïve
- 6,62 s
Le cas en détail
F(41) vaut 165 580 141, donc le nombre d'appels est 331 160 281. À 50 millions d'appels par seconde, il faut plus de 6 secondes. Une version itérative donne le même résultat avec 39 additions.
À retenir : Si une fonction récursive ralentit beaucoup quand n grandit, cherchez des sous-problèmes recalculés.
L'exemple chiffré
Valeurs utilisées dans ce cas (des exemples, pas des mesures) :
- Rang n (0 à 200) : 40
- Appels de fonction par seconde : 50000000
- Valeur de F(40)
- 102 334 155
- Appels de la version récursive naïve
- 331 160 281
- Appels avec mémorisation
- 79
- Additions de la version itérative
- 39
- Durée de la version naïve
- 6,62 s
Modifiez les champs ci-dessus pour adapter le calcul à votre situation : le résultat se met à jour tout de suite.
Comment ça se calcule
Avec fib(0) = 0 et fib(1) = 1, le nombre d'appels C(n) vérifie C(n) = 1 + C(n-1) + C(n-2), ce qui donne C(n) = 2 F(n+1) - 1. Avec mémorisation, chaque valeur n'est calculée qu'une fois : 2n - 1 appels. La version itérative fait n - 1 additions.
Les résultats sont fournis à titre indicatif, sans valeur de conseil juridique, fiscal ou financier.