Algorithmique 2 · C1 Récursivité · Chapitre 2 · 5 h

Récursif contre itératif

Transformer une boucle en récursion et l'inverse ; quand la récursion clarifie et quand elle coûte ; les appels redondants de Fibonacci naïf.

fib(40) en récursif naïf demande environ 300 millions d'appels et quelques secondes. fib(50) en demande 40 milliards, soit plusieurs minutes. La même suite, calculée par une boucle de trois lignes, donne fib(50) instantanément — et fib(1000) aussi.

Même définition mathématique, même résultat, un écart de plusieurs ordres de grandeur. Ce chapitre explique d'où vient cet écart, montre qu'il n'est pas imputable à la récursion en tant que telle, et donne les critères de choix entre les deux écritures.

Les deux écritures sont interchangeables

Commençons par le résultat théorique, qui est rassurant : toute fonction récursive peut s'écrire itérativement, et réciproquement. Le choix n'est jamais une question de puissance d'expression, seulement de lisibilité et de coût.

La transformation est même mécanique, dans les deux sens, avec deux niveaux de difficulté.

Cas facile : la récursivité terminale. Quand rien n'est en attente après l'appel, la transformation est immédiate — les paramètres deviennent des variables, l'appel devient une mise à jour, le cas de base devient la condition de sortie.

1fonction factAcc(n, acc)              fonction factIter(n)2    si n ≤ 1 alors                        acc ← 13        retourner acc                     tant que n > 1 faire4    sinon                                     acc ← n × acc5        retourner factAcc(n−1, n×acc)         n ← n − 16                                          retourner acc

Les deux colonnes font exactement la même chose, dans le même ordre, avec la même mémoire. Ce n'est pas une ressemblance : c'est ce que fait le compilateur quand il applique l'optimisation d'appel terminal du chapitre 1.

Cas général : il faut une pile explicite. Quand du travail reste en attente après l'appel, la boucle doit gérer elle-même ce que la machine gérait pour elle. C'est exactement l'exercice du chapitre précédent : on empile ce qu'on aurait suspendu, on dépile pour combiner. Le code obtenu est plus long et souvent moins clair — d'où la question suivante.

Quand la récursion clarifie

Il y a une règle simple, et elle vaut mieux que l'intuition : la récursion est le bon choix quand la définition de l'objet ou du problème est elle-même récursive.

Parcourir une arborescence de fichiers — l'exemple d'ouverture du chapitre 1 — s'écrit en cinq lignes récursives et demande une pile explicite en itératif. Un parcours d'arbre (chapitre 7), un tri par fusion (chapitre 3), les tours de Hanoï : dans tous ces cas, la version itérative est plus longue, plus difficile à relire, et plus facile à casser.

À l'inverse, parcourir un tableau, accumuler une somme, compter des occurrences sont des problèmes linéaires que la boucle exprime naturellement. Les écrire récursivement n'apporte rien et coûte une pile proportionnelle à la taille des données — la faute signalée au chapitre précédent.

Un critère opérationnel pour trancher : écrivez la définition en français. Si elle contient « … puis on recommence sur le reste », c'est une boucle. Si elle contient « … le résultat pour les sous-parties », c'est une récursion.

Le désastre de Fibonacci naïf

Reste à expliquer les 40 milliards d'appels, et l'explication n'a rien à voir avec le coût d'un appel de fonction.

1fonction fib(n)2    si n ≤ 1 alors retourner n3    retourner fib(n−1) + fib(n−2)

Cette fonction est une récursion multiple : deux appels par niveau. Son déroulé n'est plus une ligne mais un arbre d'appels, et le voir dessiné suffit à comprendre.

1                        fib(5)2                 ┌────────┴────────┐3              fib(4)             fib(3)4           ┌────┴────┐         ┌───┴───┐5        fib(3)     fib(2)   fib(2)   fib(1)6       ┌──┴──┐    ┌──┴──┐   ┌──┴──┐7    fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)8   ┌──┴──┐9fib(1) fib(0)

Comptons : fib(3) est calculé deux fois, fib(2) trois fois, fib(1) cinq fois. Et ces recalculs se recalculent eux-mêmes. Le nombre total d'appels pour fib(n) vaut $2\,\text{fib}(n{+}1) - 1$ , c'est-à-dire une quantité exponentielle : environ $1{,}6^n$ .

Le problème n'est donc pas la récursion : c'est la redondance. La même sous-question est posée un nombre exponentiel de fois, et personne ne garde la réponse. Un algorithme itératif naïf qui recalculerait tout de la même façon serait exactement aussi lent.

La preuve tient en deux lignes de correctif :

1fonction fibMemo(n, table)2    si n ≤ 1 alors retourner n3    si table[n] existe alors retourner table[n]      ← la seule ligne ajoutée4    table[n] ← fibMemo(n−1, table) + fibMemo(n−2, table)5    retourner table[n]

La fonction reste entièrement récursive, et son coût passe d'exponentiel à linéaire : chaque valeur de $n$ n'est calculée qu'une fois, les autres demandes sont servies par la table. fib(50) devient instantané sans avoir écrit une seule boucle.

Cette technique s'appelle la mémoïsation, et c'est la porte d'entrée de la programmation dynamique du chapitre 10. Retenez la leçon générale, qui vaut bien au-delà de Fibonacci : quand un algorithme récursif est lent, cherchez d'abord les recalculs, pas la récursion.

Quiz · 1 question

Pourquoi fib récursif naïf est-il exponentiel, alors que fact récursif est linéaire, tous deux étant récursifs ?

Parce que fib manipule des nombres plus grands, ce qui coûte plus cher en arithmétique — taille des nombres
Parce que fib est une récursion MULTIPLE dont l'arbre d'appels repose la même sous-question un nombre exponentiel de fois, alors que fact est une récursion simple : chaque valeur n'y est calculée qu'une fois — redondance de l'arbre d'appels
Parce que fact est optimisée en appel terminal par le compilateur, contrairement à fib — optimisation du compilateur

Réponse : fact(n) fait un seul appel par niveau : son déroulé est une ligne de n cadres, donc n appels. fib(n) en fait deux : son déroulé est un ARBRE, et cet arbre recalcule fib(3) deux fois, fib(2) trois fois, fib(1) cinq fois — et ces recalculs se recalculent. Le total vaut 2·fib(n+1) − 1, soit environ 1,6^n. Le coupable n'est donc pas la récursion mais la REDONDANCE : ajouter une table de mémoïsation, sans rien changer d'autre, ramène le coût à linéaire tout en restant récursif. Un algorithme itératif qui recalculerait de la même façon serait exactement aussi lent. La version classique de fact n'est d'ailleurs PAS terminale — la multiplication attend au retour — ce qui n'empêche rien : elle reste linéaire.

Ce que coûte vraiment un appel

Pour ne pas tomber dans l'excès inverse, il faut chiffrer ce que la récursion coûte en propre, à nombre d'opérations égal.

En temps, un appel de fonction demande d'empiler un cadre, de sauvegarder quelques registres, de brancher et de revenir : quelques nanosecondes. Sur une récursion linéaire, cela représente un surcoût de l'ordre de 20 à 50 % par rapport à la boucle équivalente. Réel, mesurable, et rarement décisif.

En espace, la différence est de nature : la boucle consomme une quantité constante, la récursion consomme $O(\text{profondeur})$ . C'est ce qui fait basculer la décision, parce qu'un dépassement de pile n'est pas une lenteur, c'est un arrêt du programme.

D'où le tableau de décision du chapitre :

Situation	Écriture à préférer
Définition récursive de l'objet (arbre, arborescence)	récursive
Diviser pour régner, profondeur logarithmique	récursive
Parcours linéaire d'une structure plate	itérative
Profondeur proportionnelle à la taille des données	itérative, ou récursion terminale
Récursion multiple avec sous-problèmes qui se répètent	récursive avec mémoïsation
Code critique en performance, profondeur faible	mesurer, puis décider

La dernière ligne n'est pas une échappatoire : c'est la règle qui vaut chaque fois que l'intuition et le profileur risquent de diverger, et le chapitre 8 du cours d'architecture a donné la raison — la loi d'Amdahl rend inutile d'optimiser ce qui ne pèse rien.

Quiz · 1 question

Une fonction récursive terminale est transformée en boucle. Qu'est-ce qui change concrètement ?

Le résultat peut différer, car l'ordre des opérations n'est plus le même — résultat différent
Rien dans le résultat ni l'ordre des opérations : seule la consommation de pile passe de O(profondeur) à O(1), les paramètres devenant des variables mises à jour — même calcul, pile constante
La version itérative est nécessairement plus lisible, ce qui justifie toujours la transformation — lisibilité garantie

Réponse : Dans une récursion terminale, rien n'est en attente après l'appel : le résultat voyage dans l'accumulateur et l'appelant n'a plus rien à faire. La transformation est donc une réécriture pure — mêmes opérations, même ordre, même résultat — dont le seul effet est de ne plus empiler de cadre : la mémoire passe de O(profondeur) à O(1). C'est exactement ce que fait un compilateur qui applique l'optimisation d'appel terminal. Quant à la lisibilité, elle dépend du problème : sur factAcc les deux versions se valent, mais sur un parcours d'arbre la version à pile explicite est nettement moins claire que la récursion — c'est pourquoi la transformation n'est pas systématiquement souhaitable.

À vous

L'exercice mesure ce que le chapitre affirme. Vous comptez les appels de fib naïf pour $n$ croissant et vous voyez l'explosion ; vous ajoutez la mémoïsation et vous constatez que le compte devient linéaire ; vous écrivez enfin la version itérative et vous comparez les trois.

Deuxième partie : transformer une récursion terminale en boucle, et vérifier que les deux versions produisent la même suite d'opérations — pas seulement le même résultat, ce qui serait un test trop faible.

Exercice de code

Comptez les appels de Fibonacci naïf, mémoïsez-le, puis transformez une récursion terminale en boucle.

Point de départ

let appels = 0;

// ── Fibonacci naïf ────────────────────────────────────────────────────────
function fibNaif(n) {
  appels++;
  if (n <= 1) return n;
  return fibNaif(n - 1) + fibNaif(n - 2);
}

// ── Fibonacci mémoïsé : la MÊME fonction, une ligne de plus ───────────────
function fibMemo(n, table = {}) {
  appels++;
  if (n <= 1) return n;
  // ← à écrire : si table[n] est déjà connu, le rendre sans recalculer
  table[n] = fibMemo(n - 1, table) + fibMemo(n - 2, table);
  return table[n];
}

// ── Fibonacci itératif ────────────────────────────────────────────────────
function fibIter(n) {
  return 0;   // ← à écrire : deux variables qui avancent, pas de tableau
}

// ── Récursion terminale et sa boucle ──────────────────────────────────────
// Les deux doivent produire la MÊME suite d'opérations, pas seulement le
// même résultat : on journalise chaque multiplication pour le vérifier.
function factAcc(n, acc = 1, journal = []) {
  if (n <= 1) { journal.push("retour " + acc); return { valeur: acc, journal }; }
  journal.push(n + " x " + acc + " = " + n * acc);
  return factAcc(n - 1, n * acc, journal);
}

function factBoucle(n) {
  const journal = [];
  let acc = 1;
  // ← à écrire : la même chose, en boucle, avec le même journal
  return { valeur: acc, journal };
}

// ── À VOUS ────────────────────────────────────────────────────────────────
// 1. Complétez fibMemo, fibIter et factBoucle.
// 2. Comparez le nombre d'appels de fibNaif et fibMemo pour n = 10, 20, 25.
//    Vérifiez que le naïf suit bien 2·fib(n+1) − 1.
// 3. Vérifiez que factAcc et factBoucle produisent des journaux IDENTIQUES.

for (const n of [10, 20, 25]) {
  appels = 0; const v = fibNaif(n); const a = appels;
  console.log("fib(" + n + ") = " + String(v).padStart(6) + " | naïf " + String(a).padStart(8) + " appels");
}

Solution

let appels = 0;

function fibNaif(n) {
  appels++;
  if (n <= 1) return n;
  return fibNaif(n - 1) + fibNaif(n - 2);
}

function fibMemo(n, table = {}) {
  appels++;
  if (n <= 1) return n;
  // LA ligne. Elle coupe toutes les branches déjà explorées de l'arbre
  // d'appels : chaque valeur de n n'est calculée qu'une seule fois.
  if (table[n] !== undefined) return table[n];
  table[n] = fibMemo(n - 1, table) + fibMemo(n - 2, table);
  return table[n];
}

function fibIter(n) {
  // Il n'y a jamais besoin que des DEUX dernières valeurs : la mémoïsation
  // garde tout le tableau, la boucle sait qu'on peut l'oublier. C'est le pas
  // suivant, et c'est ce que fera la programmation dynamique au chapitre 10.
  if (n <= 1) return n;
  let precedent = 0, courant = 1;
  for (let i = 2; i <= n; i++) {
    const suivant = precedent + courant;
    precedent = courant;
    courant = suivant;
  }
  return courant;
}

function factAcc(n, acc = 1, journal = []) {
  if (n <= 1) { journal.push("retour " + acc); return { valeur: acc, journal }; }
  journal.push(n + " x " + acc + " = " + n * acc);
  return factAcc(n - 1, n * acc, journal);
}

function factBoucle(n) {
  const journal = [];
  let acc = 1;
  // Transcription mécanique : le paramètre n devient la variable de boucle,
  // l'accumulateur devient une variable, le cas de base la condition d'arrêt.
  while (n > 1) {
    journal.push(n + " x " + acc + " = " + n * acc);
    acc = n * acc;
    n = n - 1;
  }
  journal.push("retour " + acc);
  return { valeur: acc, journal };
}

console.log("— explosion du naïf —");
for (const n of [10, 20, 25, 30]) {
  appels = 0; const v = fibNaif(n); const naif = appels;
  appels = 0; fibMemo(n); const memo = appels;
  const attendu = 2 * fibIter(n + 1) - 1;
  console.log("fib(" + String(n).padStart(2) + ") = " + String(v).padStart(7) +
    " | naïf " + String(naif).padStart(9) + " appels (formule " + String(attendu).padStart(9) + ")" +
    " | mémoïsé " + String(memo).padStart(3) +
    " | rapport " + Math.round(naif / memo) + " x");
}
// Le compte du naïf colle exactement à 2·fib(n+1) − 1, et le rapport avec la
// version mémoïsée explose. Or les deux sont RÉCURSIVES : ce n'est pas la
// récursion qui coûte, c'est de répondre deux fois à la même question.

console.log("");
console.log("— même calcul, deux écritures —");
const a = factAcc(5), b = factBoucle(5);
console.log("récursif terminal :", a.journal.join("  |  "));
console.log("boucle            :", b.journal.join("  |  "));
console.log("journaux identiques :", JSON.stringify(a.journal) === JSON.stringify(b.journal));
console.log("valeurs identiques  :", a.valeur === b.valeur);
// Identiques opération par opération : la transformation d'une récursion
// terminale en boucle n'est pas une réécriture équivalente « en gros », c'est
// la même exécution — moins les cadres empilés.

En travaux pratiques

Travaux pratiques 2 · 3 h

La même fonction, trois fois

Mesurer l'écart entre récursif naïf, mémoïsé et itératif, puis dérécursiver à la main une fonction dont le compilateur ne sait rien faire.

Avant de commencer

Le TP 1
De quoi chronométrer précisément

Énoncé

Les trois versions — Écrivez Fibonacci en récursif naïf, en récursif avec mémoïsation, et en itératif. Vérifiez qu'elles donnent le même résultat pour n de 0 à 30.
Chronométrer — Mesurez les trois pour n = 30, 40, 50, 90. Notez celles qui deviennent inutilisables et à partir de quand. Dressez le tableau. Indice : Le naïf ne passera pas n = 50. Ne l'attendez pas plus de quelques minutes.
L'espace aussi — Comparez la mémoire des trois versions. Réduisez ensuite celle de l'itératif : combien de valeurs faut-il réellement garder ?
Dérécursiver un parcours — Écrivez la somme des éléments d'un tableau en récursif, puis dérécursivez-la mécaniquement. Comparez les deux codes.
Dérécursiver avec une pile explicite — Écrivez les tours de Hanoï sans aucune récursion, en gérant vous-même une pile de tâches. Vérifiez que la sortie est identique, déplacement par déplacement. Indice : Empilez les sous-problèmes dans l'ordre INVERSE de leur exécution.
Quand la récursivité gagne — Écrivez un parcours de répertoires en récursif, puis en itératif avec pile. Comparez la longueur et la lisibilité, et dites laquelle vous garderiez.
Décider — Écrivez la règle que vous appliquerez désormais pour choisir entre les deux, en une phrase, avec les deux critères qui la déterminent.

C'est réussi quand

Le naïf et le mémoïsé donnent les mêmes valeurs, avec un écart de temps d'un facteur supérieur à mille
Votre itératif calcule fib(90) instantanément avec deux variables
Votre Hanoï à pile explicite produit exactement la même sortie que le récursif
Votre règle de décision tient en une phrase et mentionne la profondeur

Correction

Les trois versions

/* naïf : O(1,618^n) en temps, O(n) en pile */
long fib(int n) { return n < 2 ? n : fib(n-1) + fib(n-2); }

/* mémoïsé : O(n) en temps, O(n) en mémoire + O(n) en pile */
long memo[100];
long fib_m(int n) {
  if (n < 2) return n;
  if (memo[n]) return memo[n];
  return memo[n] = fib_m(n-1) + fib_m(n-2);
}

/* itératif : O(n) en temps, O(1) en mémoire */
long fib_i(int n) {
  long a = 0, b = 1;
  for (int i = 0; i < n; i++) { long t = a + b; a = b; b = t; }
  return a;
}

La mémoïsation ne change PAS l'algorithme : elle ajoute trois lignes qui suppriment la redondance. C'est le geste le plus rentable de tout le cours, et c'est exactement la programmation dynamique descendante que le TP 10 formalisera.

Les mesures

n    naïf          mémoïsé   itératif
30   0,009 s       < 1 µs    < 1 µs
40   1,1 s         < 1 µs    < 1 µs
50   135 s         < 1 µs    < 1 µs
90   ~4 000 ans    < 1 µs    < 1 µs

appels : naïf 2 692 537 pour n=30, mémoïsé 31

Trois lignes ajoutées font passer de quatre mille ans à une microseconde. Aucune optimisation de bas niveau — cache, vectorisation, assembleur — ne rattrapera jamais un écart de complexité. C'est le message central du cours, et il se mesure en une heure de TP.

La dérécursivation mécanique

/* récursif */
int somme(int *t, int n) { return n == 0 ? 0 : t[n-1] + somme(t, n-1); }

/* itératif : la récursion linéaire devient une boucle */
int somme_i(int *t, int n) {
  int s = 0;
  for (int i = 0; i < n; i++) s += t[i];
  return s;
}

Une récursion LINÉAIRE — un seul appel récursif — se transforme toujours mécaniquement en boucle. C'est le cas facile. La difficulté commence quand il y a deux appels récursifs, comme dans Hanoï ou dans un parcours d'arbre : la boucle ne suffit plus, il faut une pile.

Hanoï sans récursion

typedef struct { int n; char de, vers, par; } Tache;
Tache pile[1000]; int sommet = 0;

pile[sommet++] = (Tache){n, 'A', 'C', 'B'};

while (sommet > 0) {
  Tache t = pile[--sommet];
  if (t.n == 0) continue;
  /* ordre INVERSE : ce qu'on empile en dernier sort en premier */
  pile[sommet++] = (Tache){t.n-1, t.par, t.vers, t.de};
  pile[sommet++] = (Tache){-1, t.de, t.vers, 0};   /* l'affichage */
  pile[sommet++] = (Tache){t.n-1, t.de, t.par, t.vers};
}

On a écrit à la main ce que le processeur faisait tout seul : sauvegarder l'état, traiter, reprendre. Le code est plus long et moins clair — et il ne déborde jamais, puisque la pile est dans le tas et sa taille sous contrôle. C'est le seul argument valable pour dérécursiver, et il ne vaut que dans les cas où la profondeur peut être grande.

Quand la récursivité gagne

/* récursif : 8 lignes, se lit comme la définition du problème */
void parcourir(const char *chemin) {
  DIR *d = opendir(chemin);
  struct dirent *e;
  while ((e = readdir(d))) {
      if (est_repertoire(e)) parcourir(chemin_de(chemin, e));
      else traiter(e);
  }
  closedir(d);
}

/* itératif : 25 lignes, une pile de chemins à gérer,
 et l'ouverture/fermeture des répertoires à suivre à la main */

Sur une structure elle-même récursive — arbre, système de fichiers, expression imbriquée —, la version récursive EST la définition du problème, et la version itérative est une transcription pénible. La profondeur d'une arborescence de fichiers dépasse rarement 30 : le risque de débordement est nul, et la clarté l'emporte sans discussion.

La règle

Récursif quand la STRUCTURE est récursive et la PROFONDEUR bornée.
Itératif quand la profondeur peut être grande, ou quand
la récursion n'est qu'une boucle déguisée.

profondeur bornée   : arbre équilibré (log n), système de fichiers
profondeur non bornée : liste chaînée, entier n, arbre dégénéré

Deux critères seulement : la nature de la structure et la borne sur la profondeur. Le second est le plus souvent oublié — un parcours récursif d'arbre binaire est parfait sur un arbre équilibré et explose sur un arbre dégénéré, cas que le TP 8 vous fera rencontrer en vrai.

Ce que la suite en fait

Le bloc II tout entier repose sur ce qui vient d'être posé. Le tri fusion et le tri rapide sont des récursions multiples, exactement comme Fibonacci — mais sans redondance : les deux moitiés d'un tableau sont disjointes, donc aucune sous-question n'est posée deux fois. C'est pourquoi leur arbre d'appels donne $n \log n$ et non $1{,}6^n$ , et le chapitre 4 fera ce calcul proprement.

La mémoïsation, elle, reviendra au chapitre 10 comme première marche vers la programmation dynamique — dont l'idée entière est celle que vous venez de voir en deux lignes : ne jamais répondre deux fois à la même question.

À retenir

Flashcards · 4 cartes

Comment transforme-t-on une récursion en boucle, dans les deux cas de figure ?: Toute récursion peut s'écrire itérativement et réciproquement. Cas FACILE, la récursivité terminale : les paramètres deviennent des variables, l'appel une mise à jour, le cas de base la condition de sortie — mêmes opérations, même ordre, mais O(1) de pile au lieu de O(profondeur). Cas GÉNÉRAL, quand du travail attend après l'appel : il faut gérer soi-même une PILE EXPLICITE, ce qui donne un code plus long et souvent moins clair.
Quel critère décide entre écriture récursive et itérative ?: La récursion est le bon choix quand la DÉFINITION de l'objet ou du problème est elle-même récursive : arborescence, arbre, diviser pour régner. La boucle convient aux parcours linéaires d'une structure plate. Critère opérationnel : énoncez la définition en français — « puis on recommence sur le reste » appelle une boucle, « le résultat pour les sous-parties » appelle une récursion. Et jamais de récursion dont la profondeur est proportionnelle à la taille des données.
Pourquoi Fibonacci naïf est-il exponentiel, et quel est le vrai coupable ?: C'est une récursion MULTIPLE : deux appels par niveau, donc un arbre d'appels. Le même sous-problème y est reposé un nombre exponentiel de fois — fib(3) deux fois, fib(2) trois fois — pour un total de 2·fib(n+1) − 1 appels, soit environ 1,6^n. Le coupable n'est pas la récursion mais la REDONDANCE : ajouter une table de mémoïsation ramène le coût à linéaire SANS enlever la récursion. Quand un algorithme récursif est lent, cherchez les recalculs.
Que coûte un appel de fonction par rapport à une itération ?: En TEMPS : empiler un cadre, sauvegarder des registres, brancher, revenir — quelques nanosecondes, soit 20 à 50 % de surcoût sur une récursion linéaire. Réel, mesurable, rarement décisif. En ESPACE : la boucle consomme une quantité constante, la récursion O(profondeur). C'est cette seconde différence qui fait basculer la décision, parce qu'un dépassement de pile n'est pas une lenteur mais un arrêt du programme.