Tracer l'exécution récursive avec la pile d'appels

Introduction

Dans la leçon précédente, nous avons écrit notre première fonction récursive, FACTORIELLE, et nous avons eu un premier aperçu de son exécution avec une visualisation en "descente" et "montée". C'était une manière intuitive de se représenter le flux des appels.

Aujourd'hui, nous allons formaliser cette idée en explorant un concept fondamental en informatique : la pile d'appels (ou call stack en anglais). L'objectif est de vous apprendre à tracer manuellement l'exécution d'une fonction récursive en utilisant ce modèle. Comprendre la pile d'appels est essentiel, car c'est exactement le mécanisme que l'ordinateur utilise pour gérer les appels de fonctions, et en particulier les appels récursifs. Cette compétence vous permettra de "penser comme l'ordinateur" et de déboguer des algorithmes bien plus complexes à l'avenir.

1. Qu'est-ce que la pile d'appels ?

Quand un programme exécute une fonction, il doit garder une trace de l'endroit où il se trouve. Si cette fonction en appelle une autre, il doit se souvenir où reprendre la première fonction une fois la seconde terminée. La pile d'appels est la structure de données que l'ordinateur utilise pour gérer cette information.

Imaginez une pile d'assiettes :

• Quand vous ajoutez une assiette, vous la posez sur le dessus.
• Quand vous retirez une assiette, vous prenez celle qui est sur le dessus.

C'est un principe LIFO (Last-In, First-Out), ou "Dernier entré, premier sorti". La pile d'appels fonctionne de la même manière avec les appels de fonctions.

Pour résumer, chaque fois qu'une fonction est appelée, l'ordinateur crée un "bloc d'informations" (appelé contexte d'exécution ou frame) et le place au sommet de la pile. Ce bloc contient :

• Les paramètres de la fonction (ex: la valeur de n).
• Les variables locales à la fonction.
• L'adresse de retour (l'endroit où le programme doit continuer après la fin de la fonction).

Quand la fonction se termine, son bloc est retiré du sommet de la pile, et le programme reprend son exécution là où il s'était arrêté dans la fonction précédente.

2. Le traçage visuel de la pile d'appels

Visualisons ce processus d'empilement (quand les fonctions s'appellent) et de dépilement (quand elles retournent un résultat).

Appliquons maintenant ce modèle à notre fonction FACTORIELLE(4) de la leçon précédente.

Fonction FACTORIELLE(n : Entier) : Entier
DEBUT
    SI (n = 0) ALORS
        RETOURNER 1
    SINON
        RETOURNER n * FACTORIELLE(n - 1)
    FIN SI
FIN

Voici le déroulement sur la pile d'appels :

Voyons cela en détail :

1. Empilement :

   • FACTORIELLE(4) est appelé. Il est placé sur la pile. Pour calculer, il a besoin de FACTORIELLE(3). Il attend.
   • FACTORIELLE(3) est appelé. Il est placé au-dessus. Il a besoin de FACTORIELLE(2). Il attend.
   • FACTORIELLE(2) est appelé. Il est placé au-dessus. Il a besoin de FACTORIELLE(1). Il attend.
   • FACTORIELLE(1) est appelé. Il est placé au-dessus. Il a besoin de FACTORIELLE(0). Il attend.
   • FACTORIELLE(0) est appelé. Il est placé tout en haut de la pile. C'est le cas de base.

2. Dépilement :

   • FACTORIELLE(0) n'appelle personne. Il retourne 1. Son bloc est retiré de la pile.
   • FACTORIELLE(1) (maintenant au sommet) reçoit 1. Il peut finir son calcul : 1 * 1 = 1. Il retourne 1. Son bloc est retiré.
   • FACTORIELLE(2) (au sommet) reçoit 1. Il calcule 2 * 1 = 2. Il retourne 2. Son bloc est retiré.
   • FACTORIELLE(3) (au sommet) reçoit 2. Il calcule 3 * 2 = 6. Il retourne 6. Son bloc est retiré.
   • FACTORIELLE(4) (au sommet) reçoit 6. Il calcule 4 * 6 = 24. Il retourne 24. Son bloc est retiré.

La pile est maintenant vide et le résultat final, 24, est obtenu.

3. Trace détaillée d'un autre exemple

Pour être sûr de bien maîtriser le mécanisme, analysons un autre exemple de manière très détaillée.

4. À vous de jouer : tracez une exécution

Votre préférence pour la pratique est une excellente habitude. Il est temps de l'appliquer. Prenez une feuille et un crayon. Voici la fonction SommeCarres de l'exercice de la leçon précédente :

Fonction SommeCarres(n : Entier) : Entier
DEBUT
    SI (n = 0) ALORS
        RETOURNER 0
    SINON
        RETOURNER n*n + SommeCarres(n - 1)
    FIN SI
FIN

Votre tâche : Tracez manuellement l'exécution de SommeCarres(3) en dessinant l'état de la pile d'appels à chaque étape, comme nous l'avons fait pour FACTORIELLE. Identifiez clairement la phase d'empilement et la phase de dépilement, ainsi que les valeurs retournées à chaque étape.

...

Solution :

Voici comment la trace devrait se présenter :

Phase d'empilement :

1. SommeCarres(3) est appelé. Il est placé sur la pile. Il attend le résultat de SommeCarres(2).
   • Pile : [SommeCarres(3)]
2. SommeCarres(2) est appelé. Il est placé sur la pile. Il attend le résultat de SommeCarres(1).
   • Pile : [SommeCarres(3), SommeCarres(2)]
3. SommeCarres(1) est appelé. Il est placé sur la pile. Il attend le résultat de SommeCarres(0).
   • Pile : [SommeCarres(3), SommeCarres(2), SommeCarres(1)]
4. SommeCarres(0) est appelé. Il est placé sur la pile. C'est le cas de base.
   • Pile : [SommeCarres(3), SommeCarres(2), SommeCarres(1), SommeCarres(0)]

Phase de dépilement :

5. SommeCarres(0) retourne 0. Son bloc est retiré.
   • Pile : [SommeCarres(3), SommeCarres(2), SommeCarres(1)]
6. SommeCarres(1) reçoit 0. Il calcule 1*1 + 0 = 1. Il retourne 1. Son bloc est retiré.
   • Pile : [SommeCarres(3), SommeCarres(2)]
7. SommeCarres(2) reçoit 1. Il calcule 2*2 + 1 = 5. Il retourne 5. Son bloc est retiré.
   • Pile : [SommeCarres(3)]
8. SommeCarres(3) reçoit 5. Il calcule 3*3 + 5 = 14. Il retourne 14. Son bloc est retiré.
   • Pile : [vide]

Le résultat final est 14. Si votre trace ressemble à cela, bravo ! Vous avez parfaitement assimilé le mécanisme.

5. L'importance pratique : le risque de "Stack Overflow"

Pourquoi est-il si important de comprendre cette pile ? Parce qu'elle n'est pas infinie. Elle a une taille limitée en mémoire. Si une fonction récursive s'appelle elle-même un trop grand nombre de fois (par exemple, si vous oubliez le cas de base ou si le problème est trop grand), la pile va déborder. C'est ce qu'on appelle une erreur de dépassement de pile (stack overflow). C'est l'une des erreurs les plus classiques en récursivité.

Comprendre la pile vous aide donc non seulement à suivre l'exécution, mais aussi à anticiper les limites de vos algorithmes récursifs.

Conclusion

Félicitations pour avoir terminé cette leçon dense ! Vous avez mis un nom et une structure sur l'intuition que nous avions développée.

Les points clés à retenir :

• La pile d'appels est la structure LIFO (Dernier entré, premier sorti) que l'ordinateur utilise pour gérer les appels de fonctions.
• Chaque appel de fonction empile un nouveau contexte d'exécution (paramètres, variables locales, adresse de retour).
• Lorsqu'une fonction se termine, son contexte est dépilé, et la valeur de retour est transmise à l'appelant.
• Tracer l'état de la pile est la méthode la plus rigoureuse pour suivre l'exécution d'un algorithme récursif.
• La taille limitée de la pile peut causer une erreur de dépassement de pile (stack overflow) si la récursion est trop profonde.

Et après ?

Maintenant que vous comprenez le fonctionnement interne de la récursivité, y compris son coût en mémoire lié à la pile, nous sommes équipés pour faire une comparaison éclairée. Dans la prochaine leçon, nous allons comparer les solutions récursives et itératives (avec des boucles) pour un même problème. Nous analyserons leurs avantages et inconvénients en termes de lisibilité, de performance et d'utilisation de la mémoire.