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 les cadres d'appel les uns au-dessus des autres, 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 boucles, 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.

Il faut dérouler cette figure, et surtout regarder la colonne de gauche plutôt que la sortie. Six cadres s'ajoutent les uns au-dessus des autres, chacun avec son propre i : 1, puis 2, 3, 4, 5, enfin 6. Le sixième trouve i > longueur(t) et retourne 0. À partir de là, plus aucun appel n'est lancé : les cadres disparaissent un par un, chacun ajoutant sa mesure à ce que le cadre du dessus vient de lui rendre. 0, puis 18, puis 22, puis 47, puis 54, enfin 66.

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 un texte, c'est le texte d'une seule lettre. 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 rapproche de 1. 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.

L'appel récursif est placé avant l'affichage, et c'est tout l'algorithme. Pendant la descente, cinq cadres s'empilent sans produire une seule ligne de sortie : chacun a atteint la ligne Renverser(t, i + 1) et attend. Le cas de base 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 apparaît d'un coup, à 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. Déplacer le Écrire d'une ligne, avant l'appel au lieu d'après, suffit à rétablir l'ordre normal : la figure permet de le vérifier en modifiant une seule ligne.

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 l'a déjà présentée sous son vrai jour : à chaque appel, la machine range sur la pile l'adresse à laquelle il faudra revenir, puis les paramètres et les variables locales du nouvel appel. Le chapitre sur l'appel de fonction détaille ce rangement instruction par instruction.

C'est ce qui explique pourquoi la récursivité fonctionne sans aucune précaution particulière : les cinq i de la figure précédente 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 43, 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 compile dans n'importe quel langage, et il ne se termine jamais.

5

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 boucles.

Les deux versions donnent 66, et le traceur donne le même nombre de pas pour les deux : 14. Le temps de calcul n'est donc pas ce qui les sépare ici. Ce qui les sépare se lit dans la colonne de gauche : 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.

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à. Le chapitre suivant en donne le premier exemple sérieux.

Vérification

Exercices type

Exercice 1 : écrire une fonction récursive SommeChiffres(n) qui rend la somme des chiffres d'un entier positif, et la vérifier sur 48127.

Exercice 2 : écrire le calcul du plus grand diviseur commun de deux entiers par la méthode d'Euclide, qui s'énonce déjà de façon récursive : le pgcd de a et b vaut a quand b est nul, et vaut sinon le pgcd de b et du reste de a par b.

Exercice 3 : écrire une fonction récursive Puissance(x, n) qui calcule x à la puissance n, pour un n entier positif ou nul.

La méthode

1. Chercher la phrase qui décrit le problème par lui-même, avant d'écrire la moindre ligne. Si cette phrase ne vient pas, le problème n'est probablement pas récursif, et une boucle suffira.
2. Poser le cas de base en premier, dans la fonction comme dans la réflexion. Un cas de base écrit après l'appel récursif ne sera jamais atteint.
3. Formuler le cas de base comme une borne, n <= 0 ou i > longueur(t), plutôt que comme une égalité, sauf à avoir vérifié que la valeur exacte sera atteinte.
4. Vérifier que l'appel réduit strictement le problème. Comparer l'argument transmis à l'argument reçu, et s'assurer que la distance au cas de base diminue à chaque fois.
5. Faire confiance à l'appel récursif en écrivant le cas récursif : supposer qu'il rend déjà la bonne réponse, et se contenter de combiner son résultat.
6. Dérouler la figure et regarder la pile, pas seulement la sortie. La hauteur maximale atteinte est le coût en mémoire de l'algorithme, et le moment où elle commence à redescendre est le cas de base.
7. Comparer avec la version itérative avant de choisir. Si la boucle tient en trois lignes et se lit aussi bien, elle est préférable.

Synthèse

• Un problème est récursif quand il se décrit par lui-même sur un cas plus petit, et cette description se recopie presque mot pour mot en pseudo-code.
• Une définition récursive tient en deux parties : un cas de base traité sans aucun appel, et un cas récursif qui se rapproche strictement de ce cas de base.
• Chaque appel possède son cadre : ses paramètres et ses variables locales lui appartiennent, et c'est pourquoi plusieurs exécutions simultanées de la même fonction ne se gênent pas.
• À la descente, rien ne se calcule : tout est produit à la remontée, dans l'ordre inverse des appels. L'affichage inversé d'une liste ne repose sur rien d'autre.
• Sans cas de base, ou avec un cas de base inatteignable, la pile sature et le programme s'arrête brutalement.
• La récursivité coûte une hauteur de pile proportionnelle au nombre d'appels imbriqués : à lisibilité égale, la version itérative est préférable.

Ce chapitre a montré une réduction d'un pas à la fois, qui économise peu. Diviser pour régner applique la même mécanique à une réduction de moitié, et le compteur de pas mesurera ce que ce changement d'échelle rapporte.