Accueil › Python › Récursivité : limite de pile et mémoïsation
Récursivité : limite de pile et mémoïsation
Algorithmique d'entretienavance
Une fonction récursive se lit en deux lignes : le cas de base, puis l'appel qui s'en rapproche.
def somme_arbre(noeud: dict | None) -> int:
if noeud is None: # cas de base
return 0
return noeud["valeur"] + somme_arbre(noeud["gauche"]) + somme_arbre(noeud["droite"])
En Python, deux faits la contraignent, et ce sont eux qu'on vous demandera.
1. La pile est limitée à mille niveaux.
import sys
sys.getrecursionlimit() # 1000 par défaut
# Au-delà : RecursionError: maximum recursion depth exceeded
Et CPython n'optimise pas la récursion terminale : la réécrire en forme terminale ne change rien. Une structure de plus de mille niveaux de profondeur impose donc une version itérative, avec une pile explicite.
2. Les recalculs se suppriment avec un décorateur.
from functools import cache
@cache # une ligne : O(2ⁿ) → O(n)
def fib(n: int) -> int:
return n if n <= 1 else fib(n - 1) + fib(n - 2)
@cache mémorise chaque résultat dans un dictionnaire dont la clé est faite des arguments — qui doivent donc être hachables. Un argument list lève TypeError: unhashable type: 'list'.
Les termes à connaître
- Cas de base
La condition qui arrête la récursion. Sans elle — ou avec un appel récursif qui ne s'en approche pas — la fonction s'appelle indéfiniment et finit sur
RecursionError. C'est la première ligne à écrire, avant l'appel récursif.- Limite de récursion
CPython limite la profondeur d'appel, à 1000 par défaut (
sys.getrecursionlimit()). Au-delà :RecursionError: maximum recursion depth exceeded. C'est une protection, pas un bug : la pile du système, elle, est bien plus étroite que la mémoire.- Absence d'optimisation terminale
CPython ne transforme pas un appel récursif terminal (dernière instruction) en boucle, contrairement à d'autres langages. Une récursion terminale consomme donc autant de pile qu'une autre : écrire la version terminale n'apporte rien en Python.
- Mémoïsation
Garder en mémoire le résultat d'un appel pour ne pas le recalculer. Transforme une récursion à sous-problèmes recouvrants — O(2ⁿ) pour Fibonacci — en O(n). En Python :
@functools.cache.- functools.cache
Décorateur (Python 3.9+) qui mémorise tous les résultats d'une fonction, sans limite de taille. C'est l'équivalent de
@lru_cache(maxsize=None). Les arguments doivent être hachables : un argumentlistlèveTypeError.- functools.lru_cache
Même principe, mais avec une taille maximale : au-delà, l'entrée la moins récemment utilisée est jetée (least recently used).
@lru_cache(maxsize=1000). Exposecache_info()(nombre de succès et d'échecs) etcache_clear().- Programmation dynamique ascendante
La même idée que la mémoïsation, mais sans récursion : on remplit un tableau des petits sous-problèmes vers les grands. Pas de limite de pile, et souvent moins de mémoire — c'est la version à proposer quand la profondeur dépasse le millier.
Cette page présente la partie essentielle de la leçon. Les exemples commentés, les pièges courants et les trois questions de quiz sont dans l'application.