La récursivité

Le chapitre précédent s'est achevé sur une promesse, celle d'une fonction qui s'appelle elle-même et de la pile d'appels qui la rend possible. Cette promesse est tenue ici, et elle se tient à l'écran plutôt que sur le papier : chaque figure de ce chapitre affiche, sous l'algorithme, les cadres d'appel côte à côte, du programme principal à l'appel en cours, avec les variables que chacun possède en propre. La récursivité est l'un des rares sujets d'algorithmique où la description écrite reste opaque tant qu'on n'a pas vu le mécanisme fonctionner. Autant commencer par le voir.

Un problème qui se décrit par lui-même

Soit un relevé de cinq mesures, et la question la plus banale qui soit : combien font-elles au total ? La réponse itérative est connue depuis le chapitre sur les tableaux : un accumulateur et un parcours. Mais il existe une autre façon de répondre, et elle tient en une phrase :

Le total d'un relevé vide vaut 0. Le total d'un relevé non vide vaut sa première mesure, plus le total de tout ce qui suit.

Cette phrase a deux propriétés remarquables. D'abord elle est complète : elle couvre tous les cas, le relevé vide et les autres. Ensuite elle se sert d'elle-même, puisque « le total de tout ce qui suit » est un total de relevé, exactement la chose que la phrase est en train de définir. Un tel énoncé s'appelle une définition récursive, et il se recopie presque mot pour mot en pseudo-code.

Le paramètre i désigne l'endroit où commence « le reste ». Total(t, 1) demande le total du relevé entier, Total(t, 2) celui de tout ce qui suit la première mesure, et ainsi de suite. Quand i dépasse la dernière case, il ne reste rien : le total vaut 0, et la fonction répond sans rien appeler.

Le même déroulé tient dans un tableau de trace, une ligne par cadre. La troisième colonne se remplit de haut en bas, pendant la descente ; la dernière se remplit de bas en haut, pendant la remontée.

Le calcul ne se fait pas à la descente. À la descente, la fonction ne calcule rien : chaque cadre pose son addition en attente et relance un appel, et la troisième colonne se remplit sans qu'un seul total soit connu. Le premier nombre réel apparaît au fond, avec le 0 du cas de base. Tout le reste est produit à la remontée, dans l'ordre inverse de la descente : 0, puis 18, 22, 47, 54, enfin 66. C'est le point qui explique le plus grand nombre de malentendus sur la récursivité, et la figure le rend visible en vingt pas.

Les deux questions qui font une définition récursive

Écrire un algorithme récursif revient à répondre à deux questions, et à rien d'autre.

Quel est le cas que l'on sait traiter sans rien appeler ? Pour le total, c'est le relevé vide, dont le total vaut 0. Pour une recherche, c'est la portion vide, où l'on ne trouve rien. Pour une nomenclature, c'est la pièce élémentaire, qui ne se décompose plus. Ce cas doit être traité en premier dans la fonction, avant tout appel, sans quoi il ne sera jamais atteint.

Comment se ramener à un cas plus petit ? Il ne suffit pas d'appeler la fonction avec des arguments différents : il faut qu'ils soient plus proches du cas de base, et que le rapprochement soit strict. i + 1 rapproche de longueur(t) + 1. n - 1 rapproche de 0. n DIV 2, le quotient entier de n par 2 (7 DIV 2 vaut 3), rapproche aussi de 0, et bien plus vite. Un appel qui ne rapproche de rien donne une récursion sans fin, et la suite du chapitre montre exactement ce que la machine en fait.

La forme générale est toujours la même :

La remontée fait apparaître ce que la descente n'a pas fait

Un second exemple rend la chose encore plus nette, parce qu'il n'y a plus de calcul du tout pour brouiller la lecture. Il s'agit d'afficher une liste d'étapes dans l'ordre inverse, sans la modifier et sans compter à rebours.

Retourner seul, sans valeur, quitte la fonction sans rien rendre : Renverser affiche, elle ne calcule rien, et c'est pourquoi son appel s'écrit seul sur sa ligne, sans flèche pour ranger un résultat.

L'appel récursif est placé avant l'affichage, et c'est tout l'algorithme. Pendant la descente, cinq cadres de Renverser s'empilent sans produire une seule ligne de sortie : quatre d'entre eux ont atteint la ligne Renverser(t, i + 1) et attendent, le cinquième est le cas de base, qui ne renvoie rien du tout. Puis la remontée commence, et chaque cadre reprend là où il s'était arrêté, sur son Écrire t[i]. La sortie n'apparaît qu'à la remontée, une ligne à chaque retour, et à l'envers : « contrôler », « serrer », « visser », « poser ».

Aucune variable ne compte à rebours, aucune boucle ne descend. L'ordre inverse est produit par la seule mécanique de la pile, qui est un rangement où le dernier arrivé est le premier servi. Il suffit de déplacer le Écrire d'une ligne, avant l'appel au lieu d'après, pour rétablir l'ordre normal :

Chaque cadre affiche maintenant son étape avant d'appeler le suivant. La sortie se remplit pendant la descente, dans l'ordre du montage, de « poser » à « contrôler », et la remontée ne produit plus rien. Les deux figures demandent le même nombre de pas, 21, et leur pile monte aussi haut : seule la place de l'affichage par rapport à l'appel a changé, et elle décide de tout.

C'est la même pile que celle du processeur

Le mot « pile » employé ici n'est pas une image pédagogique. Le parcours d'architecture montre la même pile côté machine : la pile y réserve un cadre à chaque fragment de code qui en a besoin, et l'appel de fonction montre qu'une fonction qui en appelle une autre, ce que fait toute fonction récursive, range dans son cadre l'adresse à laquelle elle devra revenir et les valeurs qu'elle veut retrouver après l'appel.

C'est ce qui explique pourquoi la récursivité fonctionne sans aucune précaution particulière : les cinq i des figures précédentes ne se gênent pas, parce que chacun vit dans un cadre distinct. La portée, vue au chapitre sur les fonctions, n'est pas une règle qui s'ajoute à la récursivité, c'est ce qui la rend possible. Une fonction récursive n'est rien d'autre qu'une fonction ordinaire dont plusieurs exécutions se trouvent en cours en même temps.

Cette même pile explique aussi la limite. Chaque cadre occupe de la place, et cette place n'est pas infinie.

Cette fonction ne sert à rien d'autre qu'à creuser : elle descend de 20 à 0 et recompte les étages en remontant. Le compteur de pas affiche 64, et la pile atteint 22 cadres au plus profond, le programme principal compris. La figure la montre entièrement, ce qui donne une idée assez juste de ce qu'un algorithme récursif consomme en mémoire : une hauteur de pile proportionnelle au nombre d'appels imbriqués.

Quand la récursion ne s'arrête pas

Le défaut le plus courant est aussi le plus facile à produire : oublier le cas de base. L'algorithme est alors parfaitement lisible, il se traduirait sans une erreur dans n'importe quel langage, et il ne se termine jamais.

Rien dans cette fonction ne dit quand s'arrêter. Compte(5) appelle Compte(4), qui appelle Compte(3), et la descente continue dans les négatifs sans que quoi que ce soit s'y oppose. Le moteur de la page interrompt le déroulement à trente appels imbriqués et l'annonce, ce qui permet de voir la trace s'arrêter plutôt que de lire qu'elle le ferait : la sortie s'est rendue jusqu'à −24, et la pile est pleine.

Le second défaut est plus sournois, parce que le cas de base est bien là. Il est simplement inatteignable.

Le test n = 0 existe, il est écrit en premier, et il ne servira jamais : en partant de 7 et en retirant 2 à chaque fois, les valeurs prises sont 7, 5, 3, 1, puis −1, et la suite passe à côté de zéro sans jamais l'atteindre. La trace le montre sans ambiguïté, elle descend jusqu'à −51 avant que la pile ne sature.

Récursif ou itératif : ce que chacun coûte

Tout algorithme récursif peut s'écrire avec une boucle, et réciproquement. Le choix n'est donc jamais une question de possibilité, seulement de lisibilité et de coût. Le total du relevé s'écrit aussi comme au chapitre sur les tableaux.

Les deux versions donnent 66, la récursive en 20 pas et l'itérative en 14 : l'écart existe, mais il reste modeste, et le temps de calcul n'est pas ce qui les sépare vraiment. Ce qui les sépare se lit dans la rangée des cadres, sous l'algorithme : la version itérative tient dans un seul cadre du début à la fin, la version récursive en occupe sept au plus profond. Sur cinq mesures la différence est anecdotique ; sur cinquante mille, la version récursive épuise la pile et la version itérative ne bronche pas.

Le vrai arbitrage. La récursivité coûte de la mémoire de pile, proportionnelle à la profondeur des appels. Elle se paie en échange d'un algorithme qui ressemble à l'énoncé du problème. Le calcul est gagnant quand la description récursive est nettement plus simple que la version itérative, et perdant quand la version itérative tient en trois lignes de boucle. Un parcours linéaire de tableau appartient à la seconde catégorie : la récursivité y est un exercice, pas une solution.

Il existe toutefois une famille de problèmes où la version itérative est un cauchemar et la version récursive une évidence : ceux où le problème se coupe en plusieurs sous-problèmes indépendants, et non en un seul. Un parcours d'arborescence, un découpage en deux moitiés, une exploration de possibilités : dans ces cas, écrire la boucle équivalente oblige à gérer soi-même une pile, c'est-à-dire à refaire à la main ce que la machine fait déjà. La section suivante en donne un exemple, et le tri fusion, deux chapitres plus loin, en sera l'exemple majeur.

Là où la boucle ne suffit plus

Une nomenclature décrit un produit par ses composants : un vélo se compose d'un cadre et de deux roues ; une roue, d'une jante, de trente-deux rayons et d'un moyeu ; un moyeu, d'un axe et de deux roulements. Combien de pièces élémentaires faut-il approvisionner pour un vélo ? La question se décrit par elle-même, comme le total d'un relevé. Une pièce sans composant compte pour une ; un ensemble compte, pour chacun de ses composants, la quantité multipliée par le nombre de pièces de ce composant.

Pour la ranger, chaque pièce reçoit un numéro, et deux tableaux se lisent en parallèle. La case p de composants contient elle-même un tableau, la liste des composants directs de la pièce p ; la case p de quantites contient leurs nombres, dans le même ordre. Un tableau vide, [], signale une pièce élémentaire : c'est le cas de base.

Le résultat est 73 : un cadre, et deux roues de trente-six pièces chacune, puisqu'un moyeu en compte trois. Chaque cadre reçoit sa propre copie des deux tableaux, que la figure affiche avec ses variables ; seuls p, c, q, total et k changent d'un cadre à l'autre. La différence avec le total d'un relevé est dans la boucle : un même appel en lance plusieurs, un par composant, et chacun peut en lancer d'autres à son tour. La rangée des cadres s'allonge et se raccourcit au fil des composants, et atteint cinq cadres au plus profond : le programme principal, le vélo, la roue, le moyeu et l'une de ses pièces.

Aucune boucle seule ne ferait ce travail. Des boucles imbriquées supposeraient de savoir combien de niveaux compte la nomenclature, or un moyeu peut contenir un sous-ensemble, qui en contient un autre, sans limite fixée d'avance. Et une boucle qui descendrait d'un niveau à la fois ne saurait pas où reprendre après avoir fini une roue : il lui faudrait tenir elle-même la liste des ensembles commencés et des composants qui leur restent, c'est-à-dire refaire à la main la pile des appels que la figure affiche. La récursivité s'impose ici, parce que le problème se coupe en plusieurs sous-problèmes du même genre et que leur profondeur n'est pas connue d'avance.

Mettre en pratique

Ce que coûte un algorithme récursif se compte : les appels, la hauteur de la pile, les pas du déroulement. Tout se déduit des figures du chapitre, sans en dérouler de nouvelle.