Fibonacci de 10 : combien d'appels ?
Calculer fib(10) de façon naïve demande 177 appels pour obtenir 55.
Par Jimenez Julien, éditeur de Calepin Binaire · mis à jour le
- Valeur de F(10)
- 55
- Appels de la version récursive naïve
- 177
- Appels avec mémorisation
- 19
- Additions de la version itérative
- 9
- Durée de la version naïve
- 3,54 µs
Le cas en détail
Le nombre d'appels est 2 × F(11) - 1 = 2 × 89 - 1 = 177. Pour un si petit rang, cela reste sans conséquence. Mais l'écart avec les 9 additions d'une version itérative est déjà net.
À retenir : Sur de petits rangs, tout paraît instantané : poussez n pour voir la différence.
L'exemple chiffré
Valeurs utilisées dans ce cas (des exemples, pas des mesures) :
- Rang n (0 à 200) : 10
- Appels de fonction par seconde : 50000000
- Valeur de F(10)
- 55
- Appels de la version récursive naïve
- 177
- Appels avec mémorisation
- 19
- Additions de la version itérative
- 9
- Durée de la version naïve
- 3,54 µ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.