En Python, la profondeur de la pile d'appels récursifs est limitée par défaut (généralement à 1000). On peut consulter cette limite via la fonction sys.getrecursionlimit(). Si un algorithme dépasse ce seuil, l'interpréteur lève une exception RecursionError.

Bien qu'il soit possible d'augmenter cette limite manuellement avec sys.setrecursionlimit(), cette approche est risquée car elle peut entraîner une consommation excessive de mémoire, voire un plantage brutal du processus (Stack Overflow) si la mémoire physique est saturée. Une solution plus élégante consiste à transformer la récursion en itération ou à utiliser une technique appelée Tail Call Optimization (TCO).

Comprendre la Récursion Terminale

La récursion terminale se produit lorsque l'appel récursif est la toute dernière opération effectuée par la fonction. À ce moment précis, le résultat renvoyé par l'appel récursif est directement renvoyé par la fonction parente, sans transformation supplémentaire.

Considérons cet exemple classique de calcul de la suite de Fibonacci qui n'est pas une récursion terminale :

def fib_standard(n):
    if n < 2:
        return n
    return fib_standard(n - 1) + fib_standard(n - 2)

Ici, l'interpréteur doit attendre les résultats de deux appels distincts puis efefctuer une addition. L'état de chaque fonction doit donc rester en mémoire dans la pile.

Voici une version en récursion terminale :

def fib_terminal(n, courant=0, suivant=1):
    if n == 0:
        return courant
    return fib_terminal(n - 1, suivant, courant + suivant)

Cependant, contrairement à des langages comme Haskell ou certains compilateurs C++, l'interpréteur Python standard (CPython) n'optimise pas nativement la récursion terminale. Même avec la structure ci-desssus, la pile continuera de croître jusqu'à l'erreur de profondeur.

Simulation de la TCO avec un décorateur

Pour contourner cette limitation, nous pouvons utiliser un décorateur sophistiqué qui détourne le mécanisme de gestion des cadres de pile (stack frames) de Python pour transformer la récursion en une boucle while.

import sys

class RelaiRecursif(Exception):
    def __init__(self, args, kwargs):
        self.args = args
        self.kwargs = kwargs

def optimiser_tail_call(fonction_cible):
    def wrapper(*args, **kwargs):
        cadre_actuel = sys._getframe()
        # On vérifie si l'on est déjà dans un appel récursif optimisé
        if (cadre_actuel.f_back and 
            cadre_actuel.f_back.f_back and 
            cadre_actuel.f_code == cadre_actuel.f_back.f_back.f_code):
            raise RelaiRecursif(args, kwargs)
        
        while True:
            try:
                return fonction_cible(*args, **kwargs)
            except RelaiRecursif as e:
                # On met à jour les arguments pour l'itération suivante
                args = e.args
                kwargs = e.kwargs
    return wrapper

@optimiser_tail_call
def fib_infini(n, a=0, b=1):
    if n == 0:
        return a
    return fib_infini(n - 1, b, a + b)

# Test de dépassement de limite
# fib_infini(2000, 0, 1) s'exécutera sans erreur.

Mécanisme interne et gestion des Frames

Pour comprendre pourquoi ce code fonctionne, il faut s'intéresser aux objets internse de l'interpréteur :

• Code Object : Représentation statique du bytecode de la fonction.
• Function Object : L'instance de la fonction créée lors de la définition (def).
• Frame Object : L'état d'exécution d'un appel de fonction (pile locale, variables, pointeur d'instruction).

Le décorateur fonctionne selon une logique de capture et de rebond :

1. Lors du premier appel, le décorateur entre dans une boucle while True.
2. L'appel à la fonction réelle est tenté.
3. Si la fonction tente de s'appeler elle-même récursivement, le décorateur détecte que le f_code (le bytecode) du "grand-parent" de la frame actuelle est identique au sien.
4. Au lieu de créer un nouveau cadre de pile, il lève une exception personnalisée RelaiRecursif contenant les nouveaux arguments.
5. L'exception remonte la pile, "nettoyant" les cadres intermédiaires, jusqu'à être capturée par la boucle while du premier appel.
6. Les arguments sont mis à jour, et la boucle relance la fonction, évitant ainsi l'empilement de nouveaux cadres de pile.

Avec cette technique, l'empreinte mémoire reste constante car on ne conserve au maximum que trois cadres de pile simultanément, quel que soit le nombre d'itérations récursives demandées. Cela permet d'exécuter des algorithmes récursifs sur des dizaines de milliers de niveaux sans jamais atteindre la limite du système.