Utiliser la mémoïsation pour éviter de recalculer des sous-problèmes
Transformer une fonction récursive qui recalcule plusieurs fois les mêmes sous-problèmes en une version mémoïsée avec un dictionnaire, et justifier le gain de complexité obtenu.

Les points essentiels
- La mémoïsation consiste à stocker dans une structure (le plus souvent un dictionnaire Python) le résultat de chaque sous-problème déjà résolu, afin de le réutiliser au lieu de le recalculer.
- Elle n'est utile que si les sous-problèmes se chevauchent : la même instance (mêmes arguments) est demandée plusieurs fois dans l'arbre des appels récursifs.
Les mots à connaître
- Sous-problème
- Instance plus petite du même problème, dont la solution sert à construire celle du problème initial. Par exemple, calculer fib(5) est un sous-problème de fib(6).
- Mémoïsation
- Technique qui consiste à enregistrer le résultat d'un appel de fonction pour un jeu d'arguments donné, afin de renvoyer directement ce résultat si les mêmes arguments se présentent de nouveau.
Un exemple pour comprendre
La suite de Fibonacci est définie par fib(0)=0, fib(1)=1 et fib(n)=fib(n-1)+fib(n-2) pour n>=2. Écrire une version récursive naïve, compter les appels pour fib(5), puis écrire une version mémoïsée et compter les calculs effectués.
Version naïve : def fib(n): return n if n < 2 else fib(n-1) + fib(n-2). Pour fib(5), le nombre d'appels C(n) vérifie C(0)=C(1)=1 et C(n)=1+C(n-1)+C(n-2), d'où C(2)=3, C(3)=5, C(4)=9, C(5)=15 : 15 appels, dont fib(3) calculé 2 fois, fib(2) 3 fois, fib(1) 5 fois. Version mémoïsée : def fib_memo(n, memo=None): if memo is None: memo = {}; if n in memo: return memo[n]; if n < 2: return n; memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo); return memo[n]. Les valeurs 2, 3, 4 et 5 ne sont calculées qu'une fois chacune (les cas de base 0 et 1 sont immédiats), donc 4 calculs d'addition au lieu de 14 additions pour la version naïve. Dans la version mémoïsée, le nombre d'appels devient linéaire en n, alors qu'il croît exponentiellement dans la version naïve.

