Principe et mécanisme de la récursivité

Écrivez, avec les seuls outils d'Algorithmique 1, un algorithme qui affiche tous les fichiers d'un répertoire et de ses sous-répertoires. Une boucle parcourt le répertoire. Une boucle imbriquée parcourt chaque sous-répertoire. Une troisième les sous-sous-répertoires. Et il en faut une de plus dès qu'un utilisateur crée un dossier un cran plus bas.

Le problème n'est pas la difficulté : c'est que la profondeur n'est pas connue à l'écriture. Aucun nombre fixe de boucles imbriquées ne convient. Il manque un outil, et c'est celui de ce chapitre.

Prévenons tout de suite : la récursivité est le point qui coince de ce semestre, sans concurrence. Elle ne résiste pas parce qu'elle est compliquée — sa définition tient en deux lignes — mais parce qu'elle demande de suivre un mécanisme, l'empilement des appels, que le code ne montre pas. Tant que ce mécanisme n'est pas visualisé, le bloc II restera opaque. D'où le poids de ce chapitre, et l'insistance sur le déroulé pas à pas.

Deux clauses, et pas une de plus

Une fonction récursive est une fonction qui s'appelle elle-même. Pour qu'elle termine, elle doit comporter exactement deux sortes de clauses.

Le cas de base rend un résultat sans appel récursif. C'est la seule chose qui arrête la descente, et c'est la première ligne à écrire.

Le cas récursif se ramène au même problème sur une entrée strictement plus proche du cas de base, et combine le résultat obtenu.

1fonction fact(n)2    si n ≤ 1 alors            ← cas de base3        retourner 14    sinon                     ← cas récursif5        retourner n × fact(n − 1)

Ce qui rend cette écriture légitime n'est pas une astuce mais une définition mathématique. $n!$ se définit par $0! = 1$ et $n! = n \times (n-1)!$ ; le code ne fait que transcrire la définition. C'est la vraie force de la récursivité : quand un objet se définit récursivement, l'algorithme qui le traite s'écrit presque sans réfléchir.

Et beaucoup d'objets se définissent ainsi. Une liste est vide, ou bien un élément suivi d'une liste. Un arbre est une feuille, ou bien un nœud portant des sous-arbres. Un répertoire contient des fichiers et des répertoires. Les chapitres 5, 7 et 9 exploiteront tous ce fait ; l'introduction de ce chapitre en était déjà un cas.

La pile d'exécution

Voici le mécanisme, et c'est sur lui qu'il faut passer du temps.

Chaque appel de fonction — récursif ou non — crée un cadre d'appel (stack frame) sur la pile d'exécution : une zone contenant les paramètres, les variables locales et l'adresse de retour, c'est-à-dire l'endroit exact où reprendre. C'est la région « pile » de l'image mémoire décrite au chapitre 3 du cours de systèmes, et elle croît vers le bas.

Le point que la lecture du code ne montre pas : dans retourner n × fact(n − 1), la multiplication ne peut pas être faite au moment de l'appel. Son second facteur n'existe pas encore. L'appel courant est donc suspendu au milieu de son calcul, son cadre reste en place, et un nouveau cadre s'empile par-dessus.

Déroulons fact(4) en entier.

Trois observations à tirer de ce déroulé, et ce sont elles qui débloquent tout le reste.

Il y a quatre variables n en mémoire simultanément, valant 4, 3, 2 et 1. Chaque appel a les siennes. C'est le contresens le plus fréquent : croire qu'il n'existe qu'un n qui changerait de valeur.

Rien ne se calcule à la descente. Les quatre multiplications ont lieu à la remontée, dans l'ordre inverse des appels : $2 \times 1$, puis $3 \times 2$, puis $4 \times 6$. Un algorithme récursif fait souvent son travail au retour, pas à l'aller.

Le dernier empilé est le premier dépilé. La pile est une structure LIFO, celle du chapitre 6 — et ce n'est pas une coïncidence de vocabulaire, c'est le même objet.

Prouver que ça s'arrête

Une fonction récursive mal écrite ne boucle pas indéfiniment : elle épuise la pile et le programme est tué. Sous Linux, le message est Segmentation fault, et il est trompeur — il suggère un problème de mémoire alors que c'est un problème de terminaison.

La preuve d'arrêt suit toujours le même schéma, et il faut prendre l'habitude de l'écrire.

On exhibe une mesure — un variant — qui est un entier positif ou nul, et l'on montre deux choses : cette mesure décroît strictement à chaque appel récursif, et le cas de base est atteint lorsqu'elle ne peut plus décroître. Une suite d'entiers positifs strictement décroissante étant finie, la descente s'arrête.

Pour fact(n), le variant est $n$ lui-même : il passe de $n$ à $n-1$, et le cas de base répond dès $n \le 1$.

Trois fautes classiques se détectent avec ce schéma en main, et il vaut mieux les connaître par leur nom.

Le cas de base absent. fact sans le test s'appellerait indéfiniment.

Le cas de base inatteignable. fact avec si n = 0 au lieu de si n ≤ 1 fonctionne pour les entiers positifs et part à l'infini pour fact(-3), puisque le variant décroît sans jamais franchir 0. Le cas de base doit couvrir toutes les entrées où l'on cesse de descendre, pas seulement celles auxquelles on pense.

Le variant qui ne décroît pas. Appeler fact(n) au lieu de fact(n − 1), ou récurser sur une liste dont on n'a pas retiré la tête, produit exactement la même boucle.

Quatre formes de récursivité

Simple : un seul appel récursif par exécution du cas récursif. C'est fact. La pile croît linéairement, et le déroulé est une simple descente puis une remontée.

Multiple : plusieurs appels. C'est Fibonacci — fib(n) = fib(n−1) + fib(n−2) — et les tris du chapitre 3. Le déroulé n'est plus une ligne mais un arbre d'appels, ce qui change radicalement le coût : le chapitre suivant montrera que Fibonacci naïf recalcule des milliers de fois les mêmes valeurs.

Croisée (ou mutuelle) : deux fonctions s'appellent l'une l'autre. L'exemple d'école est le couple pair / impair, où pair(n) rend impair(n − 1). Le raisonnement de terminaison est inchangé — il faut simplement un variant qui décroisse sur le cycle complet.

Terminale : l'appel récursif est la toute dernière opération, sans aucun calcul en attente après lui.

1fonction factAcc(n, acc)          ← version terminale2    si n ≤ 1 alors3        retourner acc4    sinon5        retourner factAcc(n − 1, n × acc)     ← rien après l'appel

La différence est capitale. Dans la version classique, le cadre doit survivre pour effectuer la multiplication au retour. Ici, l'appelant n'a plus rien à faire : la multiplication a déjà eu lieu, son résultat voyage dans l'accumulateur. Le cadre peut donc être réutilisé au lieu d'être empilé, ce qui ramène la consommation mémoire à une constante. C'est l'optimisation d'appel terminal, que les compilateurs de langages fonctionnels garantissent et que gcc applique souvent en -O2 — sans le promettre, ce que le cours de programmation rappellera.

Ce que la récursion coûte

Il faut être précis sur ce point, parce que c'est là qu'on décide de l'employer ou non.

En temps, un appel de fonction coûte quelques nanosecondes : empiler le cadre, sauvegarder des registres, brancher, revenir. Négligeable une fois, sensible sur des millions d'appels.

En espace, la récursion coûte un cadre par niveau de profondeur. Une récursion de profondeur $n$ occupe $O(n)$ de pile — pour fact(4), quatre cadres ; pour fact(100000), cent mille, et la pile déborde. C'est la vraie limite, et elle est brutale : la pile d'un fil d'exécution fait typiquement 8 Mio, ce qui plafonne la profondeur autour de quelques dizaines ou centaines de milliers d'appels.

D'où la règle de choix qui vaudra pour tout le semestre : la récursion est excellente quand la profondeur est logarithmique — diviser pour régner, parcours d'arbre équilibré — et dangereuse quand elle est linéaire en la taille des données. Parcourir un tableau d'un million d'éléments récursivement est une faute ; le trier récursivement ne descend qu'à une profondeur de vingt.

À vous

L'exercice matérialise ce que l'animation a montré. Vous écrivez d'abord deux fonctions récursives simples, puis vous les réécrivez avec une pile explicite — un tableau que vous empilez et dépilez à la main.

C'est l'exercice qui débloque le plus d'étudiants, pour une raison précise : il rend visible ce que la machine faisait de toute façon. Une fois qu'on a écrit soi-même le tableau des cadres en attente, la version récursive cesse d'être magique.

Le squelette instrumente aussi la profondeur maximale atteinte, et l'un des cas de test est volontairement mal terminé : vous verrez la garde se déclencher avant le débordement réel.

// Un compteur de profondeur, pour voir la pile monter.
let profondeur = 0, maximum = 0, appels = 0;
function entrer() { appels++; profondeur++; maximum = Math.max(maximum, profondeur); }
function sortir(v) { profondeur--; return v; }
function remettreAZero() { profondeur = 0; maximum = 0; appels = 0; }

// ── 1. Récursion simple ───────────────────────────────────────────────────
function fact(n) {
  entrer();
  if (n <= 1) return sortir(1);
  return sortir(n * fact(n - 1));
}

// La somme des chiffres d'un nombre : 1234 -> 1 + 2 + 3 + 4.
function sommeChiffres(n) {
  entrer();
  return sortir(0);   // ← à écrire : cas de base n < 10, sinon n % 10 + somme(n / 10)
}

// ── 2. La MÊME chose avec une pile explicite ──────────────────────────────
// On empile les valeurs de n à la descente, on dépile en multipliant.
function factParPile(n) {
  const pile = [];
  // Descente : on n'a rien à calculer, on ne fait qu'empiler.
  for (let k = n; k > 1; k--) pile.push(k);
  // Remontée : on dépile dans l'ordre INVERSE, comme le fait la machine.
  let resultat = 1;
  while (pile.length > 0) resultat = resultat * pile.pop();
  return resultat;
}

// ── 3. Une descente mal terminée ──────────────────────────────────────────
// Le cas de base teste une ÉGALITÉ : il est franchi par 3, 2, 1, 0 mais
// jamais par -3. Une garde évite ici le vrai débordement de pile.
function factFragile(n, garde = 0) {
  if (garde > 200) throw new Error("descente infinie : cas de base jamais atteint");
  if (n === 0) return 1;
  return n * factFragile(n - 1, garde + 1);
}

// ── À VOUS ────────────────────────────────────────────────────────────────
// 1. Écrivez sommeChiffres, et vérifiez la profondeur atteinte.
// 2. Écrivez hanoi(n, de, vers, via) : affichez les déplacements, et
//    comptez-les. Combien pour n = 10 ? Quelle est la profondeur maximale ?
// 3. Corrigez factFragile pour qu'elle refuse proprement une entrée négative.

remettreAZero();
console.log("fact(6) =", fact(6), "| profondeur max", maximum, "| appels", appels);
console.log("factParPile(6) =", factParPile(6));
remettreAZero();
console.log("sommeChiffres(1234) =", sommeChiffres(1234), "| profondeur max", maximum);
try { factFragile(-3); } catch (e) { console.log("factFragile(-3) :", e.message); }

let profondeur = 0, maximum = 0, appels = 0;
function entrer() { appels++; profondeur++; maximum = Math.max(maximum, profondeur); }
function sortir(v) { profondeur--; return v; }
function remettreAZero() { profondeur = 0; maximum = 0; appels = 0; }

function fact(n) {
  entrer();
  if (n <= 1) return sortir(1);
  return sortir(n * fact(n - 1));
}

function sommeChiffres(n) {
  entrer();
  // Variant : n lui-même, divisé par 10 à chaque appel. Il décroît
  // strictement et le cas de base n < 10 est forcément atteint.
  if (n < 10) return sortir(n);
  return sortir((n % 10) + sommeChiffres(Math.floor(n / 10)));
}

function factParPile(n) {
  const pile = [];
  for (let k = n; k > 1; k--) pile.push(k);
  let resultat = 1;
  while (pile.length > 0) resultat = resultat * pile.pop();
  return resultat;
}

// Les tours de Hanoï : récursion MULTIPLE, deux appels par niveau. La
// profondeur reste n, mais le nombre d'appels double à chaque niveau.
function hanoi(n, de, vers, via, mouvements) {
  entrer();
  if (n === 0) return sortir(undefined);
  hanoi(n - 1, de, via, vers, mouvements);
  mouvements.push(de + " -> " + vers);
  hanoi(n - 1, via, vers, de, mouvements);
  return sortir(undefined);
}

function factSure(n) {
  // Le cas de base couvre TOUT ce qui est sous le seuil, pas seulement 0.
  if (n < 0) throw new Error("factorielle non définie sur les négatifs");
  if (n <= 1) return 1;
  return n * factSure(n - 1);
}

remettreAZero();
console.log("fact(6) =", fact(6), "| profondeur max", maximum, "| appels", appels);
console.log("factParPile(6) =", factParPile(6), "  (même résultat, pile écrite à la main)");

remettreAZero();
console.log("sommeChiffres(1234) =", sommeChiffres(1234), "| profondeur max", maximum);

console.log("");
console.log("— tours de Hanoï —");
for (const n of [3, 10, 20]) {
  remettreAZero();
  const m = [];
  hanoi(n, "A", "C", "B", m);
  console.log("n = " + String(n).padStart(2) +
    " | " + String(m.length).padStart(7) + " déplacements" +
    " | " + String(appels).padStart(8) + " appels" +
    " | profondeur max " + maximum);
}
// Le contraste est le point de l'exercice. La PROFONDEUR reste égale à n —
// donc la pile ne déborde pas — mais le NOMBRE D'APPELS double à chaque
// niveau : 2^n − 1 déplacements. Récursion multiple ne veut pas dire pile
// profonde ; cela veut dire arbre d'appels large, et c'est le sujet du
// chapitre suivant.

console.log("");
try { factSure(-3); } catch (e) { console.log("factSure(-3) :", e.message); }
console.log("factSure(6) =", factSure(6));

En travaux pratiques

fact(5) → 5 * fact(4)          descente : rien n'est calculé
fact(4) → 4 * fact(3)                   avant d'atteindre le fond
  fact(3) → 3 * fact(2)
    fact(2) → 2 * fact(1)
      fact(1) → 1                CAS DE BASE
    fact(2) = 2 * 1  = 2         remontée : tout se calcule ici
  fact(3) = 3 * 2  = 6
fact(4) = 4 * 6  = 24
fact(5) = 5 * 24 = 120

5 cadres empilés simultanément

static int prof = 0;

long fact(int n) {
  for (int i = 0; i < prof; i++) printf("  ");
  printf("→ fact(%d)\n", n);
  prof++;

  long r = (n <= 1) ? 1 : n * fact(n - 1);

  prof--;
  for (int i = 0; i < prof; i++) printf("  ");
  printf("← fact(%d) = %ld\n", n, r);
  return r;
}

long fact(int n) { return n * fact(n - 1); }   /* jamais d'arrêt */

Segmentation fault

(gdb) bt
#0  fact (n=-174231) at f.c:3
#1  fact (n=-174230) at f.c:3
…
#174236 fact (n=5)

environ 174 000 cadres, puis la pile de 8 Mo est épuisée

n     appels
10        177
20     21 891
30  2 692 537
35 29 860 703        ~5 secondes

nombre d'appels ≈ 2 × fib(n), donc croissance EXPONENTIELLE
en environ 1,618 puissance n

arbre pour n=5 : fib(3) calculé 2 fois, fib(2) 3 fois, fib(1) 5 fois

hanoi(n, de, vers, par) {
  if (n == 0) return;
  hanoi(n-1, de, par, vers);
  printf("déplacer %d : %c → %c\n", n, de, vers);
  hanoi(n-1, par, vers, de);
}

n  déplacements
1        1
3        7
10   1 023
20 1 048 575        = 2^n - 1

/* NON terminale : il reste une multiplication APRÈS l'appel */
long fact(int n) { return n <= 1 ? 1 : n * fact(n - 1); }

/* terminale : l'appel est la DERNIÈRE opération */
long fact_t(int n, long acc) { return n <= 1 ? acc : fact_t(n-1, n*acc); }

profondeur maximale atteinte :
fact    -O0 : ~174 000     -O2 : ~174 000
fact_t  -O0 : ~174 000     -O2 : ILLIMITÉE

/* en -O2, gcc transforme l'appel terminal en SAUT :
 le cadre est réutilisé, la pile ne croît plus */

Ce que la suite en fait

Le chapitre 2 met la récursion en balance avec l'itération : quand elle clarifie, quand elle coûte, et comment passer de l'une à l'autre. Il ouvrira surtout le dossier Fibonacci, dont l'arbre d'appels justifie à lui seul le chapitre 4 et la programmation dynamique du chapitre 10.

Tout le bloc II en dépend directement. Le tri fusion et le tri rapide sont deux récursions multiples, et leur analyse consiste à compter les niveaux de l'arbre d'appels que vous venez de dérouler. Enfin, la pile de ce chapitre reviendra comme structure de données au chapitre 6 : vous l'aurez alors rencontrée deux fois, comme mécanisme puis comme objet.

À retenir