Récursif contre itératif

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.

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 :

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.

À 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.

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");
}

En travaux pratiques

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