Pour additionner les entiers de $1$ à $n$, il suffit de savoir additionner ceux de $1$ à $n-1$, puis d’ajouter $n$. Pour additionner ceux de $1$ à $n-1$, il suffit de savoir additionner ceux de $1$ à $n-2$… et ainsi de suite jusqu’à $0$, dont la somme est connue d’avance. Une fonction récursive s’appelle elle-même sur une version plus petite du problème :
Deux ingrédients suffisent : un cas de base, assez simple pour être résolu sans appel, et la garantie que chaque appel s’en rapproche. Pour le reste, on écrit la fonction en supposant qu’elle marche déjà sur les problèmes plus petits. C’est exactement le raisonnement par récurrence : si $P(0)$ est vraie et si $P(n-1)$ entraîne $P(n)$, alors $P(n)$ est vraie pour tout $n$.
Quand somme(5) appelle somme(4), son calcul est suspendu : il manque encore la valeur de somme(4) pour terminer l’addition. L’ordinateur range les appels interrompus les uns sur les autres, dans une pile d’exécution (call stack), et les reprend dans l’ordre inverse, le dernier interrompu d’abord. La pile monte jusqu’au cas de base, puis redescend en propageant les valeurs.
L’arbre des appels de somme n’est qu’une chaîne : chaque appel n’en provoque qu’un seul autre. La fonction fib, qui calcule les termes de la suite de Fibonacci, s’appelle deux fois. Son arbre d’appels se ramifie, mais la pile, elle, ne contient jamais qu’une seule branche à la fois : sa hauteur est la profondeur de l’arbre, pas son nombre de nœuds.
Combien d’appels à somme l’expression somme(100) provoque-t-elle ? Et quelle hauteur maximale la pile atteint-elle pendant le calcul de fib(100) ?
$101$ appels, de somme(100) à somme(0). Pour fib(100), la pile ne dépasse pas $100$ appels : la plus longue branche descend de fib(100) à fib(1) en retirant $1$ à chaque étage. Le nombre total d’appels, lui, est astronomique (voir plus bas).
La pile a une taille limitée. Python refuse par défaut de dépasser environ mille appels imbriqués et lève alors une RecursionError : somme(5000) échoue, alors qu’une simple boucle for calcule la même chose sans le moindre souci.
… il faut d’abord comprendre la récursivité. Les informaticiens adorent ce genre de clin d’œil. Le système GNU doit son nom à un acronyme récursif, GNU’s Not Unix (« GNU n’est pas Unix »), dont la première lettre se déplie sans fin. Et le moteur de recherche Google, à qui l’on demande recursion, suggère malicieusement : « Did you mean: recursion ».
Trois tiges, des disques de tailles toutes différentes empilés sur la première, du plus grand au plus petit. Il faut tout transporter sur la dernière tige, un disque à la fois, sans jamais poser un disque sur un plus petit. Chercher une suite de mouvements à la main devient vite un casse-tête. Raisonner récursivement le dissout : pour déplacer $n$ disques, on déplace les $n-1$ du dessus sur la tige intermédiaire, on déplace le grand, puis on remet les $n-1$ par-dessus.
Le casse-tête est inventé en 1883 par le mathématicien Édouard Lucas, sous le pseudonyme de « N. Claus de Siam », anagramme de « Lucas d’Amiens ». Il l’accompagne d’une légende : dans un temple de Bénarès, des prêtres déplaceraient sans relâche 64 disques d’or, et le monde finirait quand ils auraient terminé.
Combien de mouvements faut-il ? Déplacer $n$ disques, c’est déplacer deux fois $n-1$ disques, plus le grand : $H(n)=2H(n-1)+1$ avec $H(0)=0$, d’où $H(n)=2^n-1$. On montre que c’est le minimum possible. Pour 64 disques, à un mouvement par seconde, il faudrait $2^{64}-1\approx 1{,}8\cdot 10^{19}$ secondes, soit environ 585 milliards d’années : le monde a de la marge.
Une tortue est un crayon que l’on pilote en vue subjective, avec trois ordres : A avance d’un pas, + tourne à droite d’un angle fixé, - tourne à gauche. La consigne A--A--A, avec un angle de $60°$, trace un triangle équilatéral.
Le biologiste hongrois Aristid Lindenmayer imagine en 1968 de faire pousser ces consignes. Une règle de réécriture remplace chaque lettre par un mot, par exemple A → A+A--A+A : chaque segment devient une ligne brisée de quatre segments. Appliquée à elle-même, encore et encore, la règle transforme le triangle en flocon de Koch. Ces L-systèmes (pour Lindenmayer) produisent des courbes qui remplissent le plan, des triangles troués à l’infini, et des plantes étonnamment réalistes.
La réécriture se programme en quelques lignes, et la récursivité s’y lit directement : le niveau $n$ est le niveau $n-1$ réécrit une fois de plus.
Les crochets donnent de la mémoire à la tortue : [ retient sa position et son cap, ] l’y ramène. C’est ce qui permet de dessiner des branches, puisqu’il faut bien revenir au tronc une fois une branche finie. La structure qui retient ces positions est une pile : la tortue revient toujours à la dernière position retenue, exactement comme l’ordinateur revient au dernier appel interrompu.
Un des plus vieux algorithmes connus, décrit dans les Éléments d’Euclide vers $-300$, calcule le plus grand commun diviseur de deux entiers. Il repose sur une seule remarque : si $a=bq+r$, les diviseurs communs de $a$ et $b$ sont exactement ceux de $b$ et $r$. Donc $\mathrm{pgcd}(a,b)=\mathrm{pgcd}(b,r)$, et l’on recommence avec des nombres plus petits jusqu’à ce que le reste soit nul.
En géométrie, l’algorithme découpe un rectangle : on y retire autant de carrés de côté $b$ que possible, et il reste un rectangle $b\times r$ sur lequel on recommence. Le dernier carré obtenu a pour côté le pgcd, et il pave le rectangle de départ.
Combien de divisions l’algorithme d’Euclide demande-t-il ? Le pire cas est atteint pour deux termes consécutifs de la suite de Fibonacci, où chaque quotient vaut $1$ et où l’on ne recule que d’un cran à chaque étape : essayez $89$ et $55$ dans l’animation. En 1844, Gabriel Lamé en déduit que le nombre de divisions ne dépasse jamais cinq fois le nombre de chiffres du plus petit des deux nombres. C’est souvent considéré comme le premier théorème de l’histoire de la complexité algorithmique.
En remontant les divisions, on peut aussi écrire le pgcd comme une combinaison de $a$ et $b$ : c’est l’algorithme d’Euclide étendu, que la tradition indienne appelait le « pulvérisateur ». Si $\mathrm{pgcd}(b,r)=bx+ry$ et $r=a-qb$, alors $\mathrm{pgcd}(a,b)=ay+b(x-qy)$ : l’appel récursif fournit $(x,y)$, et l’on en déduit le couple suivant.
Elle est élégante, la fonction fib, mais elle cache un piège. Pour calculer fib(5), elle calcule fib(3) deux fois, fib(2) trois fois, et ces répétitions s’accumulent d’étage en étage : le nombre d’appels croît comme les termes de la suite elle-même, c’est-à-dire exponentiellement.
Chaque nouveau terme multiplie le travail par environ $1{,}618$, le nombre d’or. Calculer fib(100) ainsi demanderait plus d’appels qu’il ne s’est écoulé de nanosecondes depuis le Big Bang. Le remède est simple : noter chaque résultat la première fois qu’on le calcule, et le relire ensuite au lieu de le recalculer. Cette mémoïsation fait tomber le coût à une centaine d’appels.
La récursivité, à elle seule, ne rend donc pas un algorithme rapide : tout dépend de la forme de l’arbre des appels. Quand les mêmes sous-problèmes reviennent sans cesse, on les mémorise, et c’est le point de départ de la programmation dynamique. Quand ils sont indépendants et rapetissent vite, on peut diviser pour régner.
La stratégie tient en trois temps : diviser le problème en morceaux indépendants, les résoudre récursivement, puis combiner les réponses.
Calculer $x^n$ en multipliant $x$ par lui-même demande $n-1$ multiplications. Mais $x^{n}=\left(x^{n/2}\right)^2$ quand $n$ est pair, et $x^{n}=x\left(x^{(n-1)/2}\right)^2$ quand il est impair : un seul appel récursif, sur un exposant deux fois plus petit, suivi d’une ou deux multiplications. La seconde animation de la pile, avec la fonction puiss, le montre : au lieu d’une chaîne de $n$ appels, une chaîne d’environ $\log_2 n$.
Élever un nombre à une puissance de l’ordre du milliard de milliards en une centaine de multiplications : c’est ce qui rend possible la cryptographie RSA, où l’on calcule sans cesse des puissances gigantesques modulo de grands nombres.
On l’a vu avec le plus grand sous-tableau, et le tri fusion, décrit par John von Neumann dès 1945, en est l’exemple le plus célèbre : trier chaque moitié, puis fusionner deux listes triées en un seul passage. Combien coûte un tel algorithme ? L’arbre des appels permet de le voir d’un coup d’œil. Supposons qu’on coupe un problème de taille $n$ en $a$ sous-problèmes de taille $n/2$, et que couper puis recombiner coûte un travail proportionnel à $n$. Au niveau $k$ de l’arbre, il y a $a^k$ sous-problèmes, chacun de taille $n/2^k$ : le travail du niveau vaut $n\,(a/2)^k$. Tout se joue donc dans la comparaison entre $a$ et $2$, c’est-à-dire entre la vitesse à laquelle les sous-problèmes se multiplient et celle à laquelle ils rapetissent.
Plus généralement, si l’on coupe en $a$ sous-problèmes de taille $n/b$ et que la combinaison coûte $\mathcal{O}(n^d)$, on compare $a$ à $b^d$ :
C’est un combat entre $a$, le rythme auquel les sous-problèmes prolifèrent, et $b^d$, le rythme auquel le travail par sous-problème fond. L’exponentiation rapide ($a=1$, $b=2$, $d=0$) et le tri fusion ($a=2$, $b=2$, $d=1$) tombent tous deux dans le cas d’égalité : $\mathcal{O}(\log n)$ et $\mathcal{O}(n\log n)$.
Couper chaque nombre en deux moitiés et calculer les quatre produits de moitiés donne $a=4$, $b=2$, $d=1$ : les feuilles dominent, et l’on retombe sur le $\mathcal{O}(n^2)$ de l’école. Diviser pour régner ne suffit pas ; il faut une idée de plus.
En 1960, lors d’un séminaire à Moscou, Andreï Kolmogorov conjecture qu’on ne peut pas multiplier deux nombres de $n$ chiffres en moins de $n^2$ opérations élémentaires. Moins d’une semaine plus tard, Anatoli Karatsouba, un étudiant de 23 ans, lui apporte un contre-exemple. Kolmogorov, enthousiaste, présente le résultat et le fait publier en 1962 ; Karatsouba ne l’apprend qu’en recevant les tirés à part.
L’idée, qui remonte à une astuce de Gauss pour les nombres complexes : écrire $x=a\cdot 10^m+b$ et $y=c\cdot 10^m+d$. Le produit demande $ac$, $bd$ et $ad+bc$, soit quatre produits en apparence. Mais $ad+bc=(a+b)(c+d)-ac-bd$ : trois produits suffisent. Appliquée récursivement, cette économie fait passer de $4$ à $3$ sous-problèmes, et le coût tombe à $\mathcal{O}(n^{\log_2 3})\approx\mathcal{O}(n^{1{,}585})$.
En 2019, David Harvey et Joris van der Hoeven ont atteint $\mathcal{O}(n\log n)$, la limite que l’on conjecture depuis les années 1970.
Toute fonction récursive peut s’écrire avec une boucle et une pile explicite : il suffit de faire soi-même ce que fait la pile d’exécution, comme la tortue avec ses crochets. Parfois, la version sans récursivité révèle même une structure que la récursivité cachait.
Les tours de Hanoï en offrent un bel exemple. Numérotons les coups à partir de $1$ : aux coups impairs, on déplace le plus petit disque, toujours dans le même sens de rotation ; aux coups pairs, un seul autre mouvement est permis, et on le joue. Mieux encore, le disque déplacé au coup $k$ se lit dans l’écriture binaire de $k$ : c’est le nombre de zéros qui la terminent, plus un. Résoudre les tours de Hanoï, c’est compter en binaire.
La suite des disques déplacés, $1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3\ldots$, est la « suite de la règle » : elle donne la hauteur des graduations d’une règle, plus longues aux centimètres, moyennes aux demi-centimètres, courtes aux millimètres. Le grand disque ne bouge qu’une fois, au milieu ; les deux moitiés de la suite, de part et d’autre, sont deux copies de la solution pour $n-1$ disques. La récursivité était là depuis le début, dessinée dans la règle.