Fibonacci récursif avec mémoïsation
La mémoïsation conserve les résultats déjà calculés.
Qu’est-ce que Fibonacci récursif avec mémoïsation ?
La mémoïsation conserve les résultats déjà calculés.
Éviter de recalculer les mêmes termes Fibonacci.
Quand l’utiliser ?
- Comprendre les algorithmes et structures de données.
- Observer chaque étape et traiter les cas limites.
- Comparer temps d’exécution et mémoire.
Code d’exemple
main.py
from functools import cache
@cache
def fibonacci(number):
if number < 2:
return number
return fibonacci(number - 1) + fibonacci(number - 2)
print(fibonacci(10))Résultat attendu
55Fonctionnement
Le cache ramène le temps exponentiel naïf à O(n), avec O(n) de mémoire.
Modifiez les valeurs et exécutez le programme avec le compilateur Python en ligne CodeUtility, sans installation locale.
Exercices pratiques
Modifiez les entrées et testez les cas limites avant d’utiliser des données plus volumineuses.
- Testez une entrée vide, un élément et des doublons.
- Affichez l’état après chaque étape.
- Comparez les performances avec une autre solution.