Appels récursifs · croissance exponentielle
La mémoire au service du calcul
Programmation dynamique · Fibonacci
Et si un algorithme pouvait se souvenir de ses calculs ? Explorez la différence entre la récursion naïve, la mémoïsation et la construction itérative d'un tableau.
✦ Tester mes connaissances · QCM⚡ Laboratoire Fibonacci
Modifiez le rang puis comparez les trois stratégies. Le nombre d'appels de la récursion naïve est calculé exactement sans exécuter des millions d'appels inutiles.
Appels récursifs avec cache
Additions effectuées · temps O(n)
📊 Comparaison du travail effectué
Pour comparer les méthodes, les barres représentent des opérations de nature différente : appels de fonction pour les deux méthodes récursives et additions pour la méthode itérative.
🧠 Construire le tableau, étape par étape
Les cases montrent les résultats intermédiaires F(0), F(1), …, F(n). Utilisez « Étape suivante » ou « Animer » pour voir la construction bottom-up.
Sélectionnez un rang et démarrez l'animation.
| Rang i | Valeur F(i) | Calcul / justification |
|---|
📚 À retenir pour le partiel
F(n) = F(n−1) + F(n−2). Les mêmes valeurs sont recalculées. Temps Θ(φⁿ), avec φ ≈ 1,618 ; pile O(n).
On conserve les résultats dans un cache et on ne résout chaque sous-problème qu'une fois. Temps O(n), mémoire O(n).
On calcule F(0), F(1), puis les termes suivants. Temps O(n), tableau O(n), ou O(1) avec seulement deux variables.