Pourquoi une pile explicite pour la récursion non terminale ?

1. La nature de la récursion non terminale : le "travail en attente"

Commençons par une définition précise, que vous pouvez retrouver dans les notes de cours du LIRMM, une ressource en français adaptée à votre préparation.

Comme le souligne le document, un appel est non terminal lorsqu'il reste du travail à effectuer après que l'appel récursif a retourné sa valeur. Reprenons notre factorielle :

return n * factorielle(n - 1)

L'opération n * ... est ce "calcul englobant" ou ce travail en attente. Pour pouvoir effectuer cette multiplication, le programme doit se souvenir de la valeur de n correspondante à chaque appel.

Où cette information est-elle stockée ? Elle est stockée sur la pile d'appels (ou call stack). Chaque fois qu'une fonction est appelée, un nouveau cadre de pile (stack frame) est empilé. Ce cadre contient les paramètres de la fonction, ses variables locales et l'adresse de retour (où continuer l'exécution après la fin de la fonction).

Dans le cas d'une récursion non terminale, la pile s'accumule :

• factorielle(4) est appelé. Un cadre est créé pour n=4. Il appelle factorielle(3).
• factorielle(3) est appelé. Un nouveau cadre est empilé pour n=3. Il appelle factorielle(2).
• ... et ainsi de suite jusqu'au cas de base.

La pile grandit à chaque appel, car chaque cadre doit être conservé pour que l'opération en attente (la multiplication) puisse être effectuée au retour.

La vidéo suivante explique très clairement pourquoi ce besoin de "se souvenir" de l'opération est la source de l'inefficacité.

2. Pourquoi une pile est-elle indispensable ? Un éclairage historique

L'idée que la récursion nécessite une structure de pile pour fonctionner n'est pas un simple détail d'implémentation. C'est une condition fondamentale découverte aux débuts de l'informatique.

L'histoire des premiers compilateurs nous offre une leçon précieuse.

Cette perspective historique est fondamentale pour un futur agrégé : la pile d'appels n'est pas un artifice, mais la solution structurelle au problème de la sauvegarde des contextes d'exécution imbriqués, qui est l'essence même de la récursion. La nature LIFO (Last-In, First-Out) d'une pile correspond parfaitement au déroulement des appels récursifs : le dernier appel à s'exécuter est le premier à retourner sa valeur et à permettre au contexte précédent de reprendre son travail.

3. La simulation de la pile d'appels

Nous arrivons maintenant au cœur de la leçon. Si nous voulons transformer une fonction récursive non terminale en une fonction itérative, nous supprimons les appels de fonction imbriqués. Ce faisant, nous perdons le mécanisme automatique de gestion de la pile fourni par le langage.

La conclusion est inéluctable : nous devons simuler nous-mêmes la pile d'appels en utilisant une structure de données de pile explicite.

Le travail en attente est parfois appelé une continuation. C'est une notion avancée mais l'idée est simple : c'est "ce qu'il reste à faire". La pile d'appels gère implicitement une pile de continuations. Notre pile explicite va stocker les informations nécessaires pour exécuter ces continuations dans le bon ordre.

Une ressource sur Stack Overflow, bien que dense, contient une explication d'une clarté remarquable à ce sujet.

Exemple conceptuel : Le parcours infixe d'un arbre binaire

Prenons un exemple classique de récursion non terminale : le parcours infixe (ou in-order) d'un arbre binaire.

def parcours_infixe_rec(noeud):
    if noeud is None:
        return
    



    # 1. Appel récursif non terminal
    parcours_infixe_rec(noeud.gauche)
    



    # 2. Travail en attente (visiter le noeud)
    print(noeud.valeur)
    



    # 3. Appel récursif non terminal
    parcours_infixe_rec(noeud.droite)

Ici, il y a deux appels non terminaux. Pour transformer cette fonction, nous devons utiliser une pile explicite pour "se souvenir" des nœuds dont nous devons encore visiter la valeur et le sous-arbre droit.

Voici l'algorithme itératif qui en résulte :

1. Initialiser une pile vide et un nœud courant à la racine de l'arbre.
2. Tant que courant n'est pas nul OU que la pile n'est pas vide :
   a. Tant que courant n'est pas nul :
   i. Empiler courant (pour s'en souvenir).
   ii. Mettre courant à courant.gauche (on simule le premier appel récursif).
   b. courant est maintenant nul. Cela signifie qu'on a atteint le fond de la branche gauche.
   i. Dépiler un nœud. C'est le nœud à visiter maintenant.
   ii. Afficher la valeur du nœud dépilé (on exécute le travail en attente).
   iii. Mettre courant à noeud.droite (on prépare la simulation du second appel récursif).

Cet algorithme simule parfaitement le comportement de la pile d'appels :

• La boucle interne while courant is not None: correspond à la phase d'expansion (empilement) de la récursion sur les fils gauches.
• Le dépilement correspond à la phase de contraction, où un appel récursif "revient", exécute son travail, puis passe à la branche droite.

Conclusion

Cette leçon a établi un principe fondamental de l'algorithmique. La distinction entre récursion terminale et non terminale n'est pas seulement théorique ; elle a des implications directes sur la manière d'implémenter des algorithmes performants.

Points clés à retenir :

• La récursion non terminale implique un "travail en attente" (une continuation) qui doit être mémorisé.
• Le mécanisme standard pour cette mémorisation est la pile d'appels implicite gérée par l'environnement d'exécution du langage.
• Cette pile a une taille finie, et une récursion profonde peut provoquer une erreur de dépassement de pile (Stack Overflow).
• Pour convertir un algorithme récursif non terminal en un algorithme itératif, il est indispensable de simuler la pile d'appels en utilisant une pile explicite (par exemple, une list en Python). Cette pile stocke les informations nécessaires pour reprendre les "continuations" dans le bon ordre (LIFO).

Dans la leçon précédente, nous avons transformé une récursion simple en une boucle. Aujourd'hui, nous avons compris pourquoi les cas plus complexes nécessitent une pile. Vous maîtrisez maintenant les deux stratégies fondamentales pour passer de la récursion à l'itération.

Dans la prochaine leçon, nous allons faire un pas en arrière pour construire nos fondations. Nous apprendrons à implémenter une liste chaînée simple. Cette structure est non seulement un pilier des entretiens techniques, mais elle est aussi le bloc de construction conceptuel pour de nombreuses autres structures, y compris les piles, les files, les arbres et les graphes que nous manipulerons tout au long de votre préparation.