Récursivité en C : comprendre la descente et la remontée

Tu places un printf après un appel récursif et les nombres sortent dans l'ordre inverse. Pourtant, ton code ne contient aucune boucle qui remonte les valeurs. Il faut suivre les appels encore en attente pour comprendre cet affichage.

Dans quel ordre les printf s'exécutent-ils ?

Le premier printf s'exécute avant de descendre ; le second attend le retour de walk(n - 1). Voici un programme assez court pour suivre chaque ligne.

#include <stdio.h>
static void walk(int n){    if (n <= 0) {        printf("base %d\n", n);        return;    }    printf("before %d\n", n);    walk(n - 1);    printf("after %d\n", n);}
int main(void){    walk(2);    return 0;}

$ gcc -std=c17 -Wall -Wextra -Werror -O0 -g walk.c -o walk$ ./walkbefore 2before 1base 0after 1after 2

walk(2) affiche before 2, puis appelle walk(1). Son dernier printf reste à faire. walk(1) fait la même chose avec walk(0). Celui-ci atteint le cas de base et retourne : walk(1) peut alors afficher after 1 et se terminer. Enfin, walk(2) reprend et affiche after 2.

Le mot « remontée » désigne cet ordre des retours. Le programme ne rembobine pas les lignes déjà exécutées et ne recommence pas la fonction depuis son début.

Quel appel est actif à chaque étape ?

Un seul des appels de notre programme exécute une instruction à la fois. Les autres attendent ou ont déjà terminé. Dans cette trace, chaque instantané se place juste avant le printf annoncé dans next ; les cases gardent la même identité pendant tout le parcours.

Les cases « terminé » rappellent l'historique. Elles ne représentent plus des variables accessibles dans une fonction en cours.

Pourquoi n retrouve-t-il 1 puis 2 au retour ?

Il ne retrouve pas une ancienne valeur : ces valeurs n'ont jamais été écrasées. L'expression n - 1 calcule un argument pour le prochain appel, sans affectation dans l'appelant. Au cas de base, trois instances distinctes du paramètre existent dans les appels de walk :

Le schéma montre les appels de walk, sans le cadre de main ni ceux de la bibliothèque. La pile d'appels est un modèle pratique pour suivre ce qui attend. Les détails des cadres machine peuvent changer avec les optimisations ; l'ordre observable de ce programme reste celui imposé par les instructions.

Une variable locale static serait partagée entre les appels. Ce n'est pas le cas du paramètre int n ici. Pour relier ce modèle à la durée de vie des objets, lis Pile et tas en C. Le passage par valeur et les pointeurs expliquent aussi pourquoi modifier un paramètre ordinaire ne modifie pas directement la variable de l'appelant.

Que change walk(--n) à la place de walk(n - 1) ?

--n diminue d'abord le paramètre de l'appel courant, puis transmet cette valeur au suivant. Les arguments de la descente sont encore 1 puis 0, mais les appels en attente ont eux aussi changé leur propre n. Remplace seulement cette expression pour le constater :

$ sed 's/walk(n - 1)/walk(--n)/' walk.c > changed.c$ gcc -std=c17 -Wall -Wextra -Werror changed.c -o changed$ ./changedbefore 2before 1base 0after 0after 1

Dans la version modifiée, l'appel parti avec 2 a déjà ramené son paramètre à 1 avant d'attendre. L'appel parti avec 1 l'a ramené à 0. Leurs derniers printf affichent donc 0 puis 1. Le passage par valeur fonctionne toujours ; c'est l'expression dans l'appelant qui a ajouté une modification.

Garde n - 1 quand tu veux transmettre une valeur plus petite tout en conservant le niveau courant pour la remontée. Quant à n--, il transmet la valeur avant la décrémentation : le prochain appel reçoit encore le même nombre positif. Avec notre cas de base, cela ne fait pas progresser la descente vers zéro.

Pourquoi le cas de base doit-il précéder le prochain appel ?

Il doit empêcher d'appeler encore la fonction quand l'entrée est déjà un cas terminal. Ici, n <= 0 affiche une ligne base puis quitte l'appel courant, avant toute soustraction. walk(0) affiche donc seulement base 0 ; walk(-1) affiche seulement base -1.

Pour une entrée positive, n - 1 rapproche chaque appel de zéro. Les deux propriétés vont ensemble : un cas d'arrêt et une progression qui l'atteint. Une condition présente dans le code ne suffit pas si les arguments s'en éloignent.

Le return de walk(0) ne quitte ni walk(1) ni main. Il revient au site qui l'a appelé. Les instructions encore à faire dans les appels parents expliquent les lignes after.

descend

Dans descend, transforme ce parcours en notifications : appelle on_enter pendant la descente et on_leave au retour. L'exercice ne demande aucun printf dans ta fonction et les callbacks peuvent être NULL. Son cas de base ne produit aucune notification, contrairement à la ligne base de notre démonstration.

Ouvrir l'exercice

Comment suivre une autre fonction récursive sur papier ?

Note chaque appel séparément, avec ses arguments et la prochaine instruction à exécuter au retour. Arrête la descente dès le cas de base, puis termine d'abord l'appel le plus récent. Écris une ligne de sortie seulement au moment où son instruction est atteinte.

Avec walk(3), prédis les lignes avant de changer main : les before descendent de 3 à 1, puis viennent base 0 et les after de 1 à 3. Vérifie ensuite dans le visualiseur ou avec gdb(1). Si une fonction contient plusieurs appels récursifs, garde aussi la position du prochain appel à traiter ; une simple colonne de valeurs ne suffit plus.

Questions fréquentes