Pourquoi les appels récursifs utilisent-ils une pile d’appels ?
Réponse courte
Chaque appel doit garder ses paramètres et son calcul en attente jusqu’au retour de l’appel suivant ; la pile conserve ces contextes et les dépile dans l’ordre inverse.
Comprendre
Conserver ce qui reste à calculer
Lorsqu’une fonction appelle une autre fonction, l’exécution de la première est suspendue. Pour reprendre correctement, le programme doit garder son contexte : paramètres, variables locales et instruction à exécuter au retour. Un appel récursif crée un nouveau contexte pour le même code, avec d’autres valeurs.
Pourquoi une pile ?
Les appels s’emboîtent : le dernier appel commencé est le premier à pouvoir se terminer. Une pile correspond à cet ordre dernier entré, premier sorti. Dans somme(3), somme(3) attend le résultat de somme(2), qui attend somme(1), qui attend somme(0). La base renvoie 0 ; les contextes sont ensuite retirés un par un et calculent 1, puis 3, puis 6.
Cette organisation explique aussi la limite pratique de profondeur : une très longue chaîne d’appels simultanés demande de conserver beaucoup de contextes. Une définition mathématique peut terminer pour une entrée sans que son exécution soit adaptée aux ressources disponibles. Pour suivre un programme récursif, note d’abord la descente des appels, puis la remontée des valeurs ; les variables des appels en attente ne se confondent pas.
Exemples
- Dans somme(3), somme(3) attend somme(2), et somme(2) attend somme(1) ; la pile garde ces calculs jusqu’au retour de somme(0).
- Une fonction palindrome appelée sur RADAR garde les comparaisons des paires extérieures en attente pendant qu’elle examine ADA puis D.
- Après le retour de somme(0), somme(1) calcule sa réponse avant que somme(2) puisse reprendre son calcul.
Pièges fréquents
- Imaginer qu’un appel récursif remplace l’appel précédent : les appels précédents restent suspendus avec leurs propres paramètres.
- Lire les retours dans l’ordre de la descente : les appels se déclenchent du plus grand problème au plus petit, mais leurs résultats remontent dans l’ordre inverse.
