RecursionError en Python : la récursion qui ne s'arrête plus

Définition

Vous écrivez une fonction qui s'appelle elle-même, vous la lancez, et au lieu d'un résultat vous récupérez un mur de texte qui répète la même ligne des centaines de fois. C'est un RecursionError : la fonction s'est rappelée trop de fois sans jamais rendre la main.

Python garde en mémoire chaque appel encore en cours, un peu comme une pile d'assiettes qu'on ne peut vider que par le haut. Cette pile a une hauteur maximale, fixée par défaut aux alentours de mille appels. Le millième appel qui n'a toujours pas rendu la main déclenche l'erreur.

Voici la version la plus directe du problème, une fonction sans aucune condition d'arrêt :

def compte(n):
    return compte(n - 1)

compte(5)

# RecursionError: maximum recursion depth exceeded

Le message ne dit presque rien : il ne nomme aucune valeur fautive, contrairement à une KeyError qui montre la clé absente ou une ValueError qui montre la valeur refusée. L'information utile se trouve dans le traceback qui l'accompagne.

La condition d'arrêt, la seule vraie cause

Face à ce mur de lignes identiques, la question à se poser est toujours la même : où s'arrête la descente ? Une fonction récursive tient sur deux pieds : le cas de base renvoie une valeur sans se rappeler lui-même, le cas récursif se rappelle sur un problème plus petit, ce qui en rapproche à chaque tour. Dès que l'un des deux manque, ou qu'il est mal écrit, plus rien n'arrête les appels.

Une factorielle illustre bien l'équilibre entre les deux :

def factorielle(n):
    if n <= 1:
        return 1                     # cas de base : la sortie
    return n * factorielle(n - 1)    # cas récursif : se rapproche de la sortie

Dans la pratique, on retrouve presque toujours l'une de ces trois erreurs. La première est un cas de base absent : aucun if ne coupe la descente. La deuxième est un cas de base inatteignable, parce que l'argument ne décroît pas ou saute par-dessus la valeur d'arrêt : n - 2 sur un nombre impair ne touchera jamais zéro. La troisième est un cas de base placé après l'appel récursif, donc évalué une fois la descente terminée, c'est-à-dire jamais.

Lire un traceback de mille lignes

Un traceback de récursion décourage avant même d'être lu : des centaines de lignes qui se ressemblent défilent à l'écran. Il se lit pourtant en trois secondes, à condition de savoir où regarder : les premières lignes nomment l'appel d'origine, les dernières nomment la fonction qui tourne en rond. Le milieu n'est que la même poignée de lignes recopiée jusqu'au plafond, il peut s'ignorer.

Le motif qui s'y répète donne d'ailleurs une bonne indication de la cause :

Les deux derniers cas surprennent, parce qu'aucun appel récursif n'apparaît dans le code écrit à la main. La méthode __getattr__ est appelée quand un attribut demandé reste introuvable : si son propre corps lit un attribut de self qui n'existe pas davantage, elle se retrouve à s'appeler elle-même. La récursion mutuelle relève de la même logique, plus discrètement encore : chacune des deux fonctions paraît irréprochable prise isolément.

Relever la limite règle rarement le problème

Face à cette erreur, le réflexe le plus courant est de repousser le plafond et de passer à autre chose.

import sys

sys.setrecursionlimit(10000)

Sur une récursion réellement sans fin, cette ligne ne change presque rien, sinon retarder l'exception de quelques appels, et parfois aggraver la situation.

Le relèvement se justifie dans un seul cas : un algorithme correct appliqué à des données réellement profondes, comme un arbre de catégories ou un document imbriqué sur des centaines de niveaux. La fonction n'est pas fautive, juste plus profonde que la pile par défaut ne l'autorise. Partout ailleurs, mieux vaut transformer la descente en boucle, avec une liste tenue à la main qui joue le rôle de la pile. Le code y gagne souvent en lisibilité, et cesse d'avoir une profondeur maximale.

Questions fréquentes

Parce que la profondeur de récursion suit la taille des données, pas leur complexité apparente. Un arbre de deux cents niveaux passe, un arbre de mille deux cents niveaux dépasse le plafond par défaut. La fonction n'est pas fausse : elle est simplement plus profonde que la pile ne l'autorise, et c'est le signe qu'une réécriture itérative s'impose.

Non, mais elle n'y bénéficie d'aucune optimisation. Contrairement à d'autres langages, Python n'élimine pas les appels terminaux : chaque appel occupe réellement une place dans la pile. La récursion garde tout son intérêt sur les structures arborescentes, où elle rend le code plus lisible qu'une boucle. Elle devient plus discutable sur un parcours linéaire, qu'une boucle while traite sans limite de profondeur.

Un print de sys.getrecursionlimit() affiche la valeur active, mille sur la plupart des installations. Mais cela ne dit rien de la profondeur réellement atteinte par une fonction donnée. La compter directement est souvent plus parlant, et la formation Python montre comment instrumenter une fonction pour la voir descendre appel après appel.