Coding Interview Prep · Leçon

Visualiser la pile d’appels

Visualiser la pile d’appels est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 2 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.

Quelle est la pile d’appels ?

Chaque appel de fonction en Python crée un cadre de pile dans la pile d’appels. Le cadre stocke les variables locales de la fonction, son adresse de retour (l’endroit où l’exécution reprend après le retour de la fonction) et le pointeur d’instruction courant. Lorsqu’une fonction retourne, son cadre est retiré de la pile et le contrôle revient à l’appelant. La pile d’appels s’étend vers le bas à chaque appel et se réduit à chaque retour.

Comprendre la pile d’appels est essentiel pour déboguer du code récursif, estimer l’utilisation de la mémoire et éviter les erreurs de débordement de pile lors d’une récursion profonde.

import traceback

def outer():
    inner()

def inner():
    # Print the current call stack
    traceback.print_stack()

outer()
# Shows: module -> outer -> inner

Observer les cadres de pile avec sys

Le module sys de Python fournit des outils pour inspecter la pile d’appels pendant l’exécution. sys._getframe(n) renvoie le cadre de pile situé n niveaux au-dessus de la fonction actuelle. Chaque cadre possède un dictionnaire f_locals contenant les variables locales et f_code.co_name contenant le nom de la fonction. Insérer des affichages de débogage dans une fonction récursive révèle comment les cadres s’accumulent puis disparaissent.

import sys

def countdown(n):
    depth = 0
    frame = sys._getframe(0)
    while frame:
        depth += 1
        frame = frame.f_back
    print(' ' * (n * 2) + f'countdown({n}) called, stack depth={depth}')
    if n <= 0:
        return
    countdown(n - 1)
    print(' ' * (n * 2) + f'countdown({n}) returning')

countdown(3)

Tracer factorial dans la pile d’appels

Tracez factorial(4) dans la pile d’appels. Les appels s’accumulent : factorial(4) appelle factorial(3), qui appelle factorial(2), qui appelle factorial(1), qui appelle factorial(0). Au niveau du cas de base, la pile compte 5 cadres. Les retours se dépilent : factorial(0) renvoie 1 ; factorial(1) renvoie 1×1=1 ; factorial(2) renvoie 2×1=2 ; factorial(3) renvoie 3×2=6 ; factorial(4) renvoie 4×6=24. La profondeur vaut n+1 et la complexité spatiale est en O(n).

def factorial(n, indent=0):
    prefix = '  ' * indent
    print(prefix + f'-> factorial({n})')
    if n == 0:
        print(prefix + '<- returns 1')
        return 1
    result = n * factorial(n - 1, indent + 1)
    print(prefix + f'<- returns {result}')
    return result

factorial(4)

Débordement de pile : limite de récursion de Python

Python lève RecursionError lorsque la pile d’appels dépasse sa limite (environ 1 000 cadres par défaut). Cela protège contre une récursion infinie qui consommerait toute la mémoire. Pour les problèmes dont la taille d’entrée est n = 10^4 ou plus, une solution récursive de profondeur O(n) échouera sans augmentation de la limite. L’équivalent itératif utilise un espace de pile en O(1), car il n’emploie qu’un seul cadre pour la fonction englobante.

import sys

print('Recursion limit:', sys.getrecursionlimit())

def deep_recursion(n):
    if n == 0:
        return 0
    return 1 + deep_recursion(n - 1)

# Safe: within limit
try:
    print(deep_recursion(900))
except RecursionError:
    print('Overflow at 900')

# Overflow
try:
    print(deep_recursion(2000))
except RecursionError:
    print('RecursionError at 2000 — limit exceeded!')

Augmenter la limite de récursion

Vous pouvez augmenter la limite de récursion de Python avec sys.setrecursionlimit(n), mais il s’agit d’une solution de fortune. La limite par défaut existe parce que chaque cadre de pile occupe de la mémoire (généralement plusieurs centaines d’octets avec CPython). Définir la limite à 10^6, puis appeler une récursion de profondeur 10^5, peut allouer des centaines de mégaoctets d’espace de pile. La bonne solution consiste généralement à convertir le code en solution itérative ou à utiliser la mémoïsation pour réduire la profondeur.

import sys

# Only increase when you are certain of the maximum depth
# and have confirmed it is safe
original = sys.getrecursionlimit()
sys.setrecursionlimit(5000)

def sum_to(n):
    if n == 0:
        return 0
    return n + sum_to(n - 1)

print(sum_to(3000))  # Works with increased limit
sys.setrecursionlimit(original)  # restore
print('Limit restored:', sys.getrecursionlimit())

La pile d’appels et la récursion mutuelle

La récursion mutuelle se produit lorsque la fonction A appelle la fonction B et que la fonction B appelle la fonction A. La pile d’appels alterne entre les cadres de A et de B. Ce schéma apparaît dans la détermination de la parité d’un nombre et dans les simulations de machines à états. Il est correct tant que la profondeur de la pile reste limitée, mais il peut être plus difficile d’en évaluer la profondeur que dans une simple récursion linéaire.

def is_even(n):
    if n == 0:
        return True
    return is_odd(n - 1)

def is_odd(n):
    if n == 0:
        return False
    return is_even(n - 1)

# Stack alternates: is_even(4)->is_odd(3)->is_even(2)->is_odd(1)->is_even(0)
print(is_even(4))  # True
print(is_odd(5))   # True
print(is_even(7))  # False

Appels terminaux et absence d’optimisation par Python

Un appel terminal est un appel récursif qui constitue la dernière opération avant le retour : aucun calcul ne le suit. Dans des langages comme Haskell ou Scheme, les appels terminaux sont optimisés en boucles (optimisation des appels terminaux, TCO), ce qui fournit un espace de pile en O(1). Python n’implémente délibérément pas TCO. Comme l’a expliqué Guido van Rossum, préserver la trace complète de la pile pour le débogage était plus important que les économies d’espace. Ainsi, en Python, le code récursif terminal utilise toujours un espace de pile en O(n).

# Tail-recursive factorial (accumulator pattern)
def factorial_tail(n, acc=1):
    if n == 0:
        return acc
    return factorial_tail(n - 1, acc * n)  # tail call

# In Python, this still uses O(n) stack space (no TCO)
# But it IS semantically tail-recursive
print(factorial_tail(6))   # 720
print(factorial_tail(10))  # 3628800

# Iterative version: same logic, O(1) stack
def factorial_iter(n):
    acc = 1
    while n > 0:
        acc *= n
        n -= 1
    return acc

print(factorial_iter(10))  # 3628800

Afficher les arbres de récursion

Visualiser l’arbre de récursion aide à repérer les sous-problèmes en double, qui sont la cible de la mémoïsation. Pour afficher simplement l’arbre, ajoutez un paramètre indent qui augmente de 2 espaces par niveau. Chaque appel affiche ses arguments à l’entrée et sa valeur de retour à la sortie. Exécuter ceci pour Fibonacci(5) montre clairement le branchement exponentiel et les appels répétés.

def fib_traced(n, indent=0):
    prefix = '  ' * indent
    print(prefix + f'fib({n})')
    if n <= 1:
        print(prefix + f'=> {n}')
        return n
    result = fib_traced(n-1, indent+1) + fib_traced(n-2, indent+1)
    print(prefix + f'=> {result}')
    return result

fib_traced(4)
# Shows the branching tree with duplicated sub-problems

Profondeur de pile = complexité spatiale

Pour toute fonction récursive, la profondeur maximale de la pile d’appels correspond à la profondeur maximale de récursion atteinte à un moment donné de l’exécution. Cette profondeur correspond directement à la complexité spatiale auxiliaire. Pour une récursion linéaire (factorial, Fibonacci, chaîne inversée), la profondeur est en O(n). Pour les algorithmes diviser pour régner (tri fusion, recherche binaire), elle est en O(log n). Pour les parcours d’arbres, elle est en O(h), où h est la hauteur de l’arbre (O(log n) pour un arbre équilibré, O(n) dans le pire des cas).

# Recursion depth = space complexity

# Linear recursion: O(n) stack
def linear_depth(n):
    if n == 0: return 0
    return 1 + linear_depth(n - 1)  # depth = n

# Logarithmic recursion: O(log n) stack
def log_depth(n):
    if n <= 1: return 0
    return 1 + log_depth(n // 2)    # depth = log2(n)

print('n=32 linear depth:', 32)
print('n=32 log depth:', log_depth(32))     # 5
print('n=1024 log depth:', log_depth(1024)) # 10

Convertir la récursion en itération avec une pile explicite

Tout algorithme récursif peut être rendu itératif en gérant explicitement la pile d’appels avec une liste Python. Au lieu de laisser l’OS gérer les cadres, empilez des « tâches » dans la liste et retirez-les avec pop dans une boucle. Cela supprime la limite de récursion de Python et réduit le coût associé à chaque cadre, au prix d’un code plus complexe. Le DFS itératif utilisant une pile explicite que nous avons vu précédemment suit exactement ce schéma.

# Recursive inorder traversal -> iterative with explicit stack
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val   = val
        self.left  = left
        self.right = right

def inorder_iterative(root):
    result = []
    stack  = []
    curr   = root
    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        result.append(curr.val)
        curr = curr.right
    return result

root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(6))
print(inorder_iterative(root))  # [1, 2, 3, 4, 6]

Résumé : pile d’appels et espace

La pile d’appels est la structure de données cachée derrière toute récursion. Sa profondeur correspond à la complexité spatiale de votre algorithme récursif. Python la limite à environ 1 000, de sorte que les algorithmes dont la profondeur de récursion est en O(n) nécessitent soit une limite augmentée (ce qui est risqué), soit une réécriture itérative. Lorsque vous écrivez du code récursif en entretien, indiquez toujours la complexité spatiale due à la pile d’appels : « Cette solution utilise un espace en O(n) pour la profondeur de récursion » ou « O(log n) pour le parcours d’un arbre équilibré ».

Vérification rapide

Évaluez votre compréhension des concepts de structures de données et d’algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.

Récapitulatif de la leçon

Dans cette leçon, vous avez appris que chaque appel récursif crée un cadre de pile contenant les variables locales et l’adresse de retour, que la profondeur maximale de la pile correspond à la complexité spatiale auxiliaire de la récursion, et que la limite de récursion de Python (environ 1 000) rend risqués les algorithmes de profondeur O(n) pour les grandes valeurs de n — convertissez-les en solutions itératives à l’aide d’une pile explicite. Nous allons maintenant comparer les solutions récursives et itératives et expliquer quand utiliser chacune.

Questions Fréquemment Posées

La leçon « Visualiser la pile d’appels » est-elle gratuite ?

Oui — le texte complet de « Visualiser la pile d’appels » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Visualiser la pile d’appels » ?

Utilisez le module sys de Python et des affichages de suivi pour observer la croissance et la réduction des cadres de pile, et comprendre les risques de débordement de pile liés à une récursivité pro… Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?

Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 2 sur 4.

Combien de temps prend la leçon « Visualiser la pile d’appels » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?

Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

Cadre de la récursivité : cas de base, confiance, construction
Visualiser la pile d’appels
Compromis entre récursivité et itération
Mémoïsation : mettre en cache les résultats récursifs

← Retour à Coding Interview Prep