On sait maintenant répéter un traitement avec les boucles et ranger de la logique réutilisable dans des fonctions. Il reste une famille de problèmes que les boucles classiques gèrent mal, celle des structures imbriquées dont on ne connaît pas la profondeur à l'avance. C'est le terrain de la récursivité.
Pour comprendre la récursivité, il faut d'abord comprendre la récursivité. <adage de développeur>
Le principe
Une fonction récursive est une fonction qui s'appelle elle-même. C'est une fonction tout à fait normale, dont l'une des instructions consiste à relancer la même fonction, sur un morceau plus petit du problème.
Prenons un cas concret. Tu veux connaître le nombre total de descendants d'une personne. Gengis Khan a des enfants, qui ont eux-mêmes des enfants, qui ont eux-mêmes des enfants... On ne sait pas à l'avance combien de générations il faut parcourir.
function compterDescendants(personne) {
let enfants = trouverLesEnfants(personne)
let total = enfants.length
enfants.forEach(function(enfant) {
total = total + compterDescendants(enfant)
})
return total
}
La fonction compterDescendants s'appelle elle-même pour chaque enfant. Si Gengis Khan a 2 enfants
et que chacun d'eux a 3 enfants, la fonction compte d'abord les 2 enfants de Gengis Khan, puis relance le même
traitement sur chacun pour y ajouter leurs 3 enfants, soit 2 + 6 = 8 descendants au total.
La condition d'arrêt
Toute fonction récursive a besoin d'un cas où elle arrête de s'appeler. Sans lui, elle tourne indéfiniment,
exactement comme une boucle infinie.
Dans l'exemple des descendants, l'arrêt est implicite. Quand une personne n'a pas d'enfants, le tableau
enfants est vide, le forEach n'exécute rien du tout et la fonction retourne 0 sans
se rappeler. La branche s'éteint d'elle-même.
Prenons un exemple plus simple, que tu peux tester toi-même.
function compteARebours(n) {
if (n <= 0) {
console.log("Décollage !")
return
}
console.log(n)
compteARebours(n - 1)
}
compteARebours(5)
// 5, 4, 3, 2, 1, Décollage !
La condition d'arrêt, c'est n <= 0. À chaque appel, n diminue de 1, donc on se
rapproche forcément de la sortie. Retire ce if et la fonction continuera avec des nombres de plus
en plus négatifs, sans jamais s'arrêter.
Une condition d'arrêt ne suffit pas si les appels ne s'en rapprochent pas. Un
compteARebours(n + 1) a beau tester n <= 0, il s'éloigne de la sortie à chaque
tour. Deux questions à se poser devant toute récursivité : quel est le cas où je m'arrête, et est-ce que
chaque appel me rapproche de ce cas ?
La pile d'appels
Quand une fonction en appelle une autre, la machine met la première en pause et note où elle devra reprendre.
Ces notes s'empilent les unes sur les autres, d'où le nom de pile d'appels. Une fonction récursive empile donc
une note par appel, et ne les dépile qu'en remontant.
Avec compteARebours(5), la machine empile 6 appels, et le tout premier ne se termine qu'une fois
tous les autres finis. Rien de dramatique. Mais cette pile a une taille limitée, de l'ordre de quelques
milliers d'appels selon les langages. Au-delà, le programme s'arrête net avec une erreur au nom devenu
célèbre : le dépassement de pile, ou stack overflow en anglais. Cette erreur est si courante qu'elle a donné
son nom au site Stack Overflow, où des générations de développeurs viennent chercher de l'aide.
Dans la vraie vie, un dépassement de pile signale presque toujours une condition d'arrêt oubliée ou mal
écrite, plutôt qu'une structure réellement trop profonde.
Fibonacci, la récursivité qui coûte cher
La suite de Fibonacci est l'exemple qu'on trouve dans tous les cours de programmation. Chaque nombre est la
somme des deux précédents, en partant de 0 et 1, ce qui donne 0, 1, 1, 2, 3, 5, 8, 13, 21, 34... On la retrouve
partout dans la nature, notamment dans le nombre de spirales que forment les graines d'un tournesol ou les
écailles d'une pomme de pin.
Sa définition est récursive par nature, donc le code s'écrit tout seul. Pour calculer le cinquième nombre de la
suite, il faut trouver le quatrième et le troisième, puis les additionner. Pour trouver le quatrième, rebelote
avec le troisième et le deuxième, et ainsi de suite jusqu'aux deux premiers, les seuls connus d'avance, qui
font office de condition d'arrêt.
function fibonacci(n) {
if (n <= 1) {
return n
}
return fibonacci(n - 1) + fibonacci(n - 2)
}
Trois lignes, élégantes, qui collent exactement à l'énoncé mathématique. Le problème, c'est ce que la machine
fait vraiment quand tu l'exécutes.
Tu as peut-être remarqué que le troisième nombre est réclamé deux fois, une fois par le cinquième et une fois
par le quatrième. La machine le recalcule intégralement les deux fois, en repartant de zéro, sans garder le
moindre souvenir du premier calcul. Et ainsi de suite à chaque niveau. Le même calcul est refait des dizaines,
puis des milliers, puis des millions de fois.
- fibonacci(10) : environ 177 appels de fonction.
- fibonacci(30) : environ 2,7 millions d'appels.
- fibonacci(40) : environ 331 millions d'appels, plusieurs secondes d'attente.
- fibonacci(50) : plusieurs dizaines de milliards d'appels, une bonne dizaine de minutes selon la machine.
Chaque unité ajoutée à n multiplie le travail par environ 1,6. On appelle ça une complexité
exponentielle. C'est traître, parce que tout va très bien sur les petites valeurs, celles avec lesquelles on
teste, et que rien n'annonce le mur qui attend un peu plus loin.
La même suite écrite avec une boucle se contente d'avancer une fois par nombre, en gardant simplement les deux
valeurs précédentes sous la main.
function fibonacci(n) {
let precedent = 0
let courant = 1
for (let i = 0; i < n; i++) {
let suivant = precedent + courant
precedent = courant
courant = suivant
}
return precedent
}
Cette version fait 50 tours de boucle pour fibonacci(50), contre plusieurs dizaines de milliards
d'appels pour la précédente. D'une dizaine de minutes, on passe à quelques microsecondes.
L'élégance d'un code ne dit rien de son coût. Une récursivité de trois lignes peut mettre un serveur à genoux là où une boucle un peu plus verbeuse répond instantanément. Si tu entends un développeur parler de complexité spatiale ou temporelle, c'est qu'il est en train d'étudier le coût de son algorithme en temps d'exécution et en mémoire, pour l'optimiser et ne pas tomber dans ce genre de piège.
La récursivité n'est pas coupable en soi. Le vrai problème ici, c'est qu'elle recalcule sans arrêt les mêmes valeurs. Il existe une parade, la mémoïsation, qui consiste à mettre en cache chaque résultat déjà calculé pour ne jamais le refaire. Avec elle, la version récursive redevient instantanée. Mais tant qu'à ajouter cette mécanique, autant se demander si une bonne vieille boucle ne suffisait pas.
Où est-ce que c'est utile ?
La récursivité se retrouve partout dans le quotidien des développeurs, dès qu'une chose peut en contenir une autre de même nature.
- Les dossiers de fichiers : un dossier contient des fichiers et d'autres dossiers, qui contiennent eux-mêmes des fichiers et des dossiers...
- Les menus de navigation : un menu contient des éléments qui sont parfois des sous-menus contenant d'autres éléments.
- Les commentaires : sur Reddit ou YouTube, un commentaire peut avoir des réponses, qui peuvent avoir des réponses, qui peuvent avoir des réponses...
- Les organigrammes : un directeur manage des responsables, qui managent des équipes, qui contiennent des collaborateurs.
- Les catégories produit : "Maison" contient "Cuisine", qui contient "Petit électroménager", sur autant de niveaux que le catalogue en demande.
Le fil rouge de tous ces exemples reste le même. Ce sont des structures en arbre, où chaque branche peut porter d'autres branches du même type. C'est le terrain de jeu naturel de la récursivité.
Certaines récursivités sont moins directes. Une fonction A appelle une fonction B, qui rappelle la fonction A. C'est bien plus difficile à repérer en lisant le code, et une mauvaise conception provoque vite une boucle infinie qui consomme toutes les ressources de la machine.
S'il ne fallait retenir qu'une chose : une fonction récursive résout un gros problème en le ramenant au même problème, en plus petit, jusqu'à un cas assez simple pour être traité directement.