La récursivité en programmation fonctionnelle

La taxonomie des dinosaures est un arbre : les Dinosauria se divisent en deux grands groupes, qui se divisent à leur tour en groupes plus petits, et au bout des branches pendent les espèces. Tu ne sais pas à l'avance combien de niveaux compte un tel arbre, donc tu ne sais pas combien de boucles imbriquer. Il faut une fonction qui traite un seul nœud, et qui se débrouille avec ses enfants en s'appelant elle-même.

La récursivité est une technique dans laquelle une fonction s'appelle elle-même. À Jurassic Park, la récursivité ressemble à l'exploration de l'arbre généalogique des dinosaures : pour connaître toute l'ascendance d'une espèce, tu dois remonter génération après génération, jusqu'à atteindre le plus ancien ancêtre.

Les bases de la récursivité

Toute fonction récursive a besoin de deux éléments :

1. Le cas de base (base case) - la condition qui termine la récursivité
2. Le cas récursif - l'appel de la fonction avec un problème simplifié

Chaque appel suit le même schéma : vérifie la condition de base et, si elle est remplie, renvoie immédiatement le résultat, sinon simplifie le problème et rappelle la fonction sur une partie plus petite. L'exemple classique est la factorielle, c'est-à-dire le produit des nombres de 1 à n :

1// Exemple classique - la factorielle
2function factorial(n) {
3  // Cas de base
4  if (n <= 1) return 1;
5  // Cas récursif
6  return n * factorial(n - 1);
7}
8
9factorial(5); // 5 * 4 * 3 * 2 * 1 = 120

La condition n <= 1 arrête la descente, et chaque appel diminue n de 1, donc on finit toujours par l'atteindre. Détaillons ce qui se passe sur la pile d'appels (call stack) pour factorial(5) :

1// Visualisation des appels :
2// factorial(5)
3//   5 * factorial(4)
4//     4 * factorial(3)
5//       3 * factorial(2)
6//         2 * factorial(1)
7//           return 1     <- cas de base
8//         return 2
9//       return 6
10//     return 24
11//   return 120

Aucune multiplication ne s'exécute tant qu'on n'a pas atteint le cas de base, et les appels précédents attendent sur la pile, chacun avec sa propre valeur de n. Sans cas de base, la fonction s'appellerait à l'infini, jusqu'à ce que le moteur interrompe le programme par une erreur de dépassement de pile : dans Chrome et Node.js, c'est RangeError: Maximum call stack size exceeded, et dans Firefox, InternalError: too much recursion.

La récursivité avec des structures arborescentes

La récursivité est naturelle pour traiter des structures de données arborescentes - comme la hiérarchie des espèces. Chaque nœud a un nom et un tableau children, et une feuille est un nœud dont le tableau d'enfants est vide :

1const dinoTaxonomy = {
2  name: 'Dinosauria',
3  children: [
4    {
5      name: 'Saurischia',
6      children: [
7        { name: 'Theropoda', children: [
8          { name: 'T-Rex', children: [] },
9          { name: 'Velociraptor', children: [] },
10        ]},
11        { name: 'Sauropoda', children: [
12          { name: 'Brachiosaurus', children: [] },
13        ]},
14      ],
15    },
16    {
17      name: 'Ornithischia',
18      children: [
19        { name: 'Triceratops', children: [] },
20        { name: 'Stegosaurus', children: [] },
21      ],
22    },
23  ],
24};

L'arbre compte quatre niveaux, mais les fonctions que nous allons écrire n'ont pas besoin de le savoir. La recherche d'une espèce fonctionne ainsi : si le nœud courant est la cible, on le renvoie, sinon on interroge tour à tour chacun de ses enfants :

1// Recherche récursive dans l'arbre
2function findSpecies(node, target) {
3  if (node.name === target) return node;
4  for (const child of node.children) {
5    const found = findSpecies(child, target);
6    if (found) return found;
7  }
8  return null;
9}
10
11findSpecies(dinoTaxonomy, 'Velociraptor');
12// { name: 'Velociraptor', children: [] }

Il y a ici deux cas de base : la découverte de la cible (node.name === target) et la feuille, pour laquelle la boucle ne s'exécute pas une seule fois, si bien que la fonction renvoie null. L'arbre reste intact, car la fonction se contente de lire. La récursivité se combine aussi très bien avec reduce, par exemple pour compter les nœuds :

1// Récursivité + reduce : on compte tous les nœuds de l'arbre
2function countNodes(node) {
3  return 1 + node.children.reduce((sum, child) => sum + countNodes(child), 0);
4}
5
6countNodes(dinoTaxonomy); // 10

Le cas de base est caché ici : pour une feuille, reduce sur un tableau vide renvoie la valeur initiale 0, donc la feuille compte pour 1 et la récursivité s'arrête. Le même squelette servira à collecter les noms des feuilles ou à construire le chemin de la racine jusqu'à une espèce. Transmets le chemin sous forme de nouveau tableau ([...path, node.name]), et non avec push, pour que les branches n'abîment pas les résultats les unes des autres.

Récursivité vs itération

En PF, la récursivité remplace les boucles. Toute boucle peut s'écrire de manière récursive. Compare deux versions de la somme des poids des dinosaures :

1// Itération - somme d'un tableau
2function sumIterative(arr) {
3  let total = 0;
4  for (const num of arr) {
5    total += num;
6  }
7  return total;
8}
9
10// Récursivité - somme d'un tableau
11function sumRecursive(arr) {
12  if (arr.length === 0) return 0;
13  const [head, ...tail] = arr;
14  return head + sumRecursive(tail);
15}
16
17// Les deux donnent le même résultat
18const weights = [8000, 150, 56000, 2500];
19sumIterative(weights); // 66650
20sumRecursive(weights); // 66650

L'écriture const [head, ...tail] = arr est une déstructuration : head reçoit le premier élément, et tail un nouveau tableau avec le reste. Le cas de base est le tableau vide, dont la somme vaut 0, et weights reste intact. JavaScript n'est pourtant pas conçu pour la récursivité profonde : chaque appel occupe un cadre de pile, et tail est à chaque fois une nouvelle copie du tableau, donc avec quelques milliers d'éléments, la pile peut s'épuiser. Mon conseil : additionne les listes plates avec reduce, et garde la récursivité pour les structures imbriquées, comme les arbres.

L'optimisation des appels terminaux (Tail Call Optimization)

La récursivité peut provoquer un dépassement de pile (stack overflow) lors d'appels profonds. Une récursivité terminale est une récursivité dans laquelle l'appel récursif est la dernière opération de la fonction. Après son retour, il ne reste plus rien à faire, donc le moteur pourrait libérer le cadre de pile courant - c'est le principe de l'optimisation des appels terminaux (TCO). Compare les deux formes de la factorielle :

1// Récursivité ordinaire - chaque appel attend le résultat du suivant
2function factorialNormal(n) {
3  if (n <= 1) return 1;
4  return n * factorialNormal(n - 1); // doit attendre le résultat
5}
6
7// Récursivité terminale - l'accumulateur transporte le résultat
8function factorialTail(n, accumulator = 1) {
9  if (n <= 1) return accumulator;
10  return factorialTail(n - 1, n * accumulator); // dernière opération
11}

Dans factorialNormal, après le retour de la récursion, il faut encore multiplier le résultat par n, donc l'appel n'est pas la dernière opération. factorialTail transporte le résultat partiel dans l'accumulateur, et grâce à cela, l'appel se trouve tout à la fin. Pour être honnête, il faut ajouter que la spécification ES2015 prévoit ces appels en mode strict, mais que seul le moteur de Safari les a implémentés. Dans Chrome, Node.js et Firefox, factorialTail(100000) fera toujours déborder la pile, donc en JavaScript, la récursivité terminale est avant tout un motif lisible avec accumulateur, et non une protection contre l'erreur.

Le motif de l'accumulateur est utile au-delà des nombres. flattenDeep aplatit une liste imbriquée à n'importe quelle profondeur, en transmettant vers le bas le même tableau de résultats :

1// Exemple pratique - aplatir une structure imbriquée
2function flattenDeep(arr, result = []) {
3  for (const item of arr) {
4    if (Array.isArray(item)) {
5      flattenDeep(item, result);
6    } else {
7      result.push(item);
8    }
9  }
10  return result;
11}
12
13const nested = [['Rex', ['Blue', 'Charlie']], 'Brachio', [['Stego']]];
14flattenDeep(nested);
15// ['Rex', 'Blue', 'Charlie', 'Brachio', 'Stego']

Array.isArray reconnaît un tableau imbriqué, et on descend alors d'un niveau. Ce n'est pas une récursivité terminale, car l'appel se trouve dans une boucle, et push modifie le tableau result. C'est toutefois un accumulateur local : le paramètre par défaut crée un nouveau tableau à chaque appel venu de l'extérieur, donc nested reste intact. En JavaScript moderne, nested.flat(Infinity) produit le même effet. Dans la leçon suivante, nous verrons comment copier des structures imbriquées sans mutation.

Retiens : la récursivité, c'est une promenade dans l'arbre généalogique - chaque pas te rapproche du but d'une génération, et le cas de base te dit quand t'arrêter.

1// La recursivite en programmation fonctionnelle
2console.log("=== Jurassic Park - Arbre Genealogique des Especes ===\n");
3
4// --- EXEMPLE 1 : Recursivite de base ---
5console.log("--- Factorielle (factorial) ---");
6
7function factorial(n) {
8  if (n <= 1) return 1;
9  return n * factorial(n - 1);
10}
11
12console.log("5! =", factorial(5));
13console.log("10! =", factorial(10));
14
15// --- EXEMPLE 2 : Arbre taxonomique ---
16console.log("\n--- Arbre taxonomique ---");
17
18const taxonomy = {
19  name: "Dinosauria",
20  children: [
21    {
22      name: "Saurischia",
23      children: [
24        { name: "Theropoda", children: [
25          { name: "T-Rex", children: [] },
26          { name: "Velociraptor", children: [] },
27          { name: "Spinosaurus", children: [] },
28        ]},
29        { name: "Sauropoda", children: [
30          { name: "Brachiosaurus", children: [] },
31          { name: "Diplodocus", children: [] },
32        ]},
33      ],
34    },
35    {
36      name: "Ornithischia",
37      children: [
38        { name: "Triceratops", children: [] },
39        { name: "Stegosaurus", children: [] },
40        { name: "Ankylosaurus", children: [] },
41      ],
42    },
43  ],
44};
45
46// Affichage recursif de l'arbre
47function printTree(node, indent = 0) {
48  console.log(" ".repeat(indent) + "- " + node.name);
49  node.children.forEach((child) => printTree(child, indent + 2));
50}
51
52printTree(taxonomy);
53
54// Recherche recursive
55function findSpecies(node, target) {
56  if (node.name === target) return node;
57  for (const child of node.children) {
58    const found = findSpecies(child, target);
59    if (found) return found;
60  }
61  return null;
62}
63
64console.log("\nTrouve:", findSpecies(taxonomy, "Velociraptor") ? "OUI" : "NON");
65console.log("Inexistant:", findSpecies(taxonomy, "Dragon") ? "OUI" : "NON");
66
67// Comptage recursif des feuilles
68function countLeaves(node) {
69  if (node.children.length === 0) return 1;
70  return node.children.reduce((sum, child) => sum + countLeaves(child), 0);
71}
72console.log("Nombre d'especes:", countLeaves(taxonomy));
73
74// --- EXEMPLE 3 : Somme recursive ---
75console.log("\n--- Somme recursive vs iteration ---");
76
77function sumRecursive(arr) {
78  if (arr.length === 0) return 0;
79  const [head, ...tail] = arr;
80  return head + sumRecursive(tail);
81}
82
83const weights = [8000, 150, 56000, 2500, 9000];
84console.log("Somme recursive:", sumRecursive(weights));
85
86// --- EXEMPLE 4 : Aplatir une structure ---
87console.log("\n--- Aplatir une structure ---");
88
89function flattenDeep(arr) {
90  return arr.reduce((result, item) => {
91    if (Array.isArray(item)) {
92      return [...result, ...flattenDeep(item)];
93    }
94    return [...result, item];
95  }, []);
96}
97
98const nested = [["Rex", ["Blue", "Charlie"]], "Brachio", [["Stego"]]];
99console.log("Aplati:", flattenDeep(nested));
100
101// --- EXEMPLE 5 : Recursivite terminale ---
102console.log("\n--- Recursivite terminale ---");
103
104function factorialTail(n, acc = 1) {
105  if (n <= 1) return acc;
106  return factorialTail(n - 1, n * acc);
107}
108
109console.log("Tail 10! =", factorialTail(10));
110console.log("Tail 20! =", factorialTail(20));