Pile d'Appels
Chaque appel de fonction crée un 'cadre' empilé en mémoire. Comprendre cette pile d'appels est essentiel pour maîtriser la récursivité et éviter les crashs de programme.
Objectifs du cours
- Comprendre le fonctionnement de la pile d'exécution
- Visualiser les appels récursifs dans la pile
- Identifier et résoudre les débordements de pile (stack overflow)
- Maîtriser la technique de récursivité terminale
- Transformer une récursion en itération
Erreurs courantes à éviter
- Oublier le cas de base causant une récursion infinie
- Ne pas comprendre l'ordre de dépilage (LIFO)
- Confondre profondeur de récursion et nombre d'appels
- Ignorer la limite de taille de la pile Python
La **pile d'exécution** est une zone mémoire qui stocke les informations sur les fonctions en cours d'exécution. Chaque appel de fonction crée un **cadre d'exécution** (stack frame) contenant :
1. **L'adresse de retour** : où reprendre après la fonction 2. **Les paramètres** : valeurs passées à la fonction 3. **Les variables locales** : créées dans la fonction 4. **L'environnement** : références aux scopes englobants
**Fonctionnement LIFO** (Last In, First Out) : - Quand on appelle une fonction → on **empile** un cadre - Quand une fonction se termine → on **dépile** son cadre - Le programme reprend au cadre précédent
**Visualisation** : Imaginez une pile d'assiettes. Vous ne pouvez retirer que l'assiette du dessus (la dernière posée).
def fonction_a():
print("Début A")
x = 10
fonction_b() # Appel de B
print("Fin A")
def fonction_b():
print("Début B")
y = 20
fonction_c() # Appel de C
print("Fin B")
def fonction_c():
print("Début C")
z = 30
print("Fin C")
# État de la pile lors de l'exécution :
fonction_a()
# 1. Appel fonction_a() → Pile: [main, fonction_a]
# 2. Appel fonction_b() → Pile: [main, fonction_a, fonction_b]
# 3. Appel fonction_c() → Pile: [main, fonction_a, fonction_b, fonction_c]
# 4. Fin fonction_c() → Pile: [main, fonction_a, fonction_b]
# 5. Fin fonction_b() → Pile: [main, fonction_a]
# 6. Fin fonction_a() → Pile: [main]
# Sortie :
# Début A
# Début B
# Début C
# Fin C
# Fin B
# Fin AQuiz de validation
1. Que contient un cadre d'exécution (stack frame) ?
2. Quel est l'ordre de dépilage des appels de fonctions ?
3. Quelle erreur obtient-on quand la récursion est trop profonde en Python ?
4. Qu'est-ce que la récursivité terminale ?
5. Comment transformer une récursion en itération ?
