La récursivité

Déplacer une tour de Hanoï de 64 disques demande 18 446 744 073 709 551 615 déplacements ; une fonction récursive décrit la solution en quatre lignes.

Une fonction qui s'appelle elle-même

Certains problèmes contiennent une copie plus petite d'eux-mêmes. La factorielle de 5, notée 5!, vaut 5 × 4 × 3 × 2 × 1 = 120. Regarde-la à nouveau : c'est 5 × (4 × 3 × 2 × 1), c'est-à-dire 5 × 4!. En général, n! = n × (n − 1)! : pour calculer une factorielle, on peut donc calculer une factorielle plus petite et multiplier. Une fonction qui résout un problème en s'appelant elle-même sur une version plus petite est récursive.

function factorial(n) {
  if (n <= 1) return 1;          // cas de base : on s'arrête ici
  return n * factorial(n - 1);   // cas récursif : un problème plus petit
}
console.log(factorial(5)); // affiche 120

Toute fonction récursive a besoin de deux parties. Le cas de base est une entrée assez petite pour qu'on y réponde directement, sans autre appel : ici, la factorielle de 1 vaut 1. Le cas récursif réduit le problème et rappelle la fonction. Chaque appel doit se rapprocher du cas de base. Sinon, par exemple si tu écrivais factorial(n + 1) par erreur, les appels ne s'arrêteraient jamais.

La pile d'appels

Comment l'ordinateur garde-t-il la trace de tous ces appels inachevés ? Quand factorial(5) s'exécute, il arrive à 5 * factorial(4) et doit attendre la réponse. L'ordinateur place l'appel en attente sur une pile, un tas où le dernier élément posé est le premier retiré. factorial(4) attend factorial(3), et ainsi de suite jusqu'à factorial(1), qui renvoie 1 tout de suite. Puis la pile se dépile : factorial(2) renvoie 2, factorial(3) renvoie 6, factorial(4) renvoie 24 et factorial(5) renvoie 120.

La pile a une taille limitée. Une récursion qui n'atteint jamais son cas de base continue d'ajouter des appels jusqu'à épuisement de la place, et JavaScript s'arrête avec une erreur ; dans Chrome et Node.js, le message est « RangeError: Maximum call stack size exceeded ». À cause de cette même limite, une récursion très profonde, sur des centaines de milliers de niveaux, s'écrit plutôt avec une boucle.

Les tours de Hanoï

Les tours de Hanoï sont un casse-tête publié par le mathématicien français Édouard Lucas en 1883. Il y a trois piquets et une pile de disques de tailles différentes sur le premier piquet, le plus grand en bas. Le but est de déplacer toute la pile sur le troisième piquet. On ne peut déplacer qu'un disque à la fois, seulement le disque du dessus d'un piquet, et on ne doit jamais poser un disque sur un plus petit.

Réfléchir étape par étape à l'endroit où va chaque disque devient vite confus. Réfléchir de façon récursive rend la solution courte. Pour déplacer n disques de A vers C : d'abord, on écarte les n − 1 disques du dessus, de A vers B. Puis on déplace le plus grand disque de A vers C. Puis on déplace les n − 1 disques de B pour les poser dessus, en C. Déplacer n − 1 disques est le même casse-tête, une taille en dessous, et déplacer un seul disque est le cas de base. Pour 3 disques, cela donne 7 déplacements ; le labo montre la pile des appels en attente à chaque déplacement.

function hanoi(n, from, to, via) {
  if (n === 0) return;
  hanoi(n - 1, from, via, to);
  console.log("disk " + n + ": " + from + " -> " + to);
  hanoi(n - 1, via, to, from);
}
hanoi(3, "A", "C", "B");  // 7 déplacements

Combien de déplacements demandent n disques ? Déplacer n disques coûte deux déplacements de n − 1 disques plus un : M(n) = 2M(n − 1) + 1, avec M(1) = 1. Cela donne 1, 3, 7, 15, 31, donc M(n) = 2ⁿ − 1, et aucune solution ne peut en utiliser moins. Dix disques demandent 1023 déplacements. Soixante-quatre disques en demandent 2⁶⁴ − 1 = 18 446 744 073 709 551 615 ; à un déplacement par seconde, cela fait environ 585 milliards d'années. C'est la croissance en O(2ⁿ) de l'unité précédente.

Récursivité, boucles et travail répété

Tout ce qui s'écrit avec la récursivité peut s'écrire avec une boucle et une pile gérée soi-même, et les cas simples comme la factorielle sont souvent plus clairs avec une boucle. La récursivité brille quand le problème a lui-même la forme d'un arbre : couper une liste dans le tri fusion, explorer des dossiers dans des dossiers, ou chercher un chemin dans un labyrinthe, le sujet de la dernière unité. Un piège est le travail répété. Les nombres de Fibonacci 0, 1, 1, 2, 3, 5, 8, … suivent fib(n) = fib(n − 1) + fib(n − 2). Écrit directement en récursif, fib(10) = 55 fait 177 appels, fib(20) en fait 21 891 et fib(30) en fait 2 692 537, car les mêmes petites valeurs sont recalculées encore et encore. Retenir les réponses déjà trouvées, ou construire à partir du bas avec une boucle, supprime ce gaspillage.