Première · Numérique et sciences informatiques

Utiliser la pile d'appels pour suivre une fonction récursive

Représenter et exploiter la pile d'appels d'une fonction récursive Python : empiler et dépiler les appels, identifier le cas de base et prévoir la valeur renvoyée à chaque retour.

Aperçu gratuit
Illustration de la fiche « Utiliser la pile d'appels pour suivre une fonction récursive »

Les points essentiels

  • Chaque appel d'une fonction crée un cadre d'exécution (frame) qui contient les paramètres, les variables locales et le point de retour ; l'interpréteur range ces cadres dans une pile d'appels.
  • Une pile est une structure LIFO (dernier entré, premier sorti) : le dernier appel empilé est le premier à se terminer et à être dépilé.

Les mots à connaître

Pile (structure LIFO)
Structure de données où l'on n'ajoute (empiler) et ne retire (dépiler) un élément qu'au sommet : le dernier élément ajouté est le premier retiré.
Pile d'appels
Pile gérée par l'interpréteur dont chaque élément est un cadre d'exécution (paramètres, variables locales, adresse de retour) correspondant à un appel de fonction non encore terminé.

Un exemple pour comprendre

Soit def fact(n): if n == 0: return 1 else: return n * fact(n - 1). Décrire la pile d'appels lors de l'exécution de fact(3) et donner le résultat.

Descente : fact(3) est empilé, il attend 3 * fact(2). On empile fact(2), qui attend 2 * fact(1), puis fact(1), qui attend 1 * fact(0), puis fact(0). La pile contient alors 4 cadres : fact(3), fact(2), fact(1), fact(0) au sommet. Cas de base : fact(0) renvoie 1 et est dépilé. Remontée : fact(1) calcule 1 * 1 = 1 et est dépilé ; fact(2) calcule 2 * 1 = 2 et est dépilé ; fact(3) calcule 3 * 2 = 6 et est dépilé. Le résultat est 6 et la profondeur maximale de pile est 4 = n + 1.

Première page de l’Essentiel : Utiliser la pile d'appels pour suivre une fonction récursive
Ketty