Appels récursifs de Fibonacci (version naïve)

Calculer fib(n) en rappelant fib(n-1) et fib(n-2) semble élégant, mais refait sans cesse les mêmes calculs. Saisissez n pour mesurer le gaspillage.

Jimenez JulienPar , éditeur de Calepin Binaire · mis à jour le

Valeur de F(30)
832 040
Appels de la version récursive naïve
2 692 537
Appels avec mémorisation
59
Additions de la version itérative
29
Durée de la version naïve
53,85 ms

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.

Questions fréquentes

Pourquoi la version naïve est-elle si lente ?

Parce qu'elle recalcule les mêmes valeurs : fib(30) calcule par exemple fib(10) des milliers de fois.

Qu'est-ce que la mémorisation ?

Conserver chaque résultat déjà calculé pour le réutiliser au lieu de le recalculer, une technique appelée aussi mémoïsation.

Cas fréquents

Des exemples déjà remplis, avec leur explication :

Intégrer cet outil sur votre site

Copiez ce code pour afficher l'outil sur votre site ou votre blog. L'outil s'exécute dans le navigateur du visiteur, sans cookie ni suivi, et affiche un lien « Propulsé par Calepin Binaire » vers cette page.

Aperçu de la version intégrable : https://mircode.org/embed/appels-recursifs-de-fibonacci-version-naive/

Les résultats sont fournis à titre indicatif. Pour aller plus loin, découvrez les sites de la catégorie Sandbox et casse-têtes de l'annuaire et lisez le guide de cette catégorie.

Autres outils

Voir les 35 outils