Formations — 1 037 leçons en français

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 argument list lève TypeError.

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). Expose cache_info() (nombre de succès et d'échecs) et cache_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.

Lire l'explication détaillée et faire le quiz →

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.