Le même problème, en plus petit
La récursivité résout un problème en confiant une version plus petite du même problème à la même méthode. Chaque appel fait sa part du travail, et sait quand s'arrêter.
Vous arrivez probablement de la leçon Arbres : chaque enfant y est la racine d'un sous-arbre, et la même méthode s'applique à chaque enfant. Cette annexe démonte le mécanisme qui rend cela possible.
Trois idées fausses à remplacer
- • « Les appels partagent leurs variables. » Non : chaque appel possède les siennes.
- • « Un return arrête toute la récursivité. » Non : il ne termine qu'un seul appel.
- • « Il faut dérouler tous les appels dans sa tête pour écrire du code récursif. » Non : trois vérifications suffisent.
La suite de cette annexe remplace ces trois idées, une par une.
Les trois ingrédients
Le plus petit exemple utile : additionner les entiers de 0 à n, avec n positif ou nul. Le premier test refuse les autres entrées. Viennent ensuite les trois ingrédients de toute méthode récursive.
Un cas de base qui arrête les appels
n == 0répond immédiatement0, sans nouvel appel. Le cas de base contient la condition d'arrêt et la réponse à la plus petite entrée.Une réduction
sumTo(n - 1)reçoit une entrée strictement plus petite, qui se rapproche du cas de base à chaque appel.Un travail local
Len +est la seule responsabilité de cet appel. Il ajoute sa propre valeur, puis confie le reste à la même méthode.
Une grille de lecture
Ces trois ingrédients sont la grille de lecture de tout code récursif du cours : Fibonacci, printTree, les trois exemples de la leçon Arbres. S'il en manque un, la méthode est cassée ; la zone « lire le symptôme » montre comment.
Chaque appel a son propre monde
Quand sumTo(3) appelle sumTo(2), le premier appel ne disparaît pas : il attend, posé sur la pile d'appels. Java empile un cadre par appel, avec ses propres paramètres et variables. Le dernier appel commencé est le premier terminé : exactement la règle LIFO de la leçon Listes, piles et files.
Les deux panneaux ci-dessous montrent la même pile, à deux moments de la même exécution.
La montée : les appels s'empilent
Sommet de la pile
Premier appel
La descente : chaque cadre rend sa réponse
Sommet de la pile
Premier appel
Quatre n indépendants
Pendant sumTo(3), quatre variables n existent en même temps : 3, 2, 1 et 0, chacune dans son cadre. Aucun appel ne modifie le n d'un autre. C'est pour la même raison que printTree, plus bas, passera depth + 1 : une nouvelle valeur pour le cadre de l'enfant, jamais un compteur partagé.
Cette trace complète sert à comprendre la machine. Pour écrire du code, vous n'aurez presque jamais à la refaire : c'est l'objet du pari de la confiance, plus bas.
Un return ne termine qu'un appel
Un return termine le cadre courant et remet sa valeur à l'appelant. À l'appelant d'en faire quelque chose… ou de la perdre. Le bug récursif le plus fréquent tient sur une ligne. Cherchons "Nora" dans une chaîne de maillons :
Relisez la version « avant » avec la pile en tête. Le cadre profond qui trouve "Nora" renvoie bien true… à son appelant direct. Mais cet appelant ignore la valeur reçue et exécute son propre return false. La bonne réponse se perd en route : la méthode ne répond true que si la cible est en tête de chaîne. La version « après » relaie la réponse de cadre en cadre jusqu'au premier appel.
void ou valeur ?
Une méthode sans valeur de retour n'a rien à relayer : l'appel seul suffit (un affichage, par exemple). Dès que la méthode renvoie quelque chose, chaque appel récursif doit être retourné, additionné ou comparé. Jamais posé seul sur sa ligne.
Fibonacci : la forme, pas le bon modèle
Les trois ingrédients sont visibles : n <= 1 arrête une branche, n - 1 et n - 2 réduisent, l'addition est le travail local. C'est l'exemple classique des cours de récursivité. Il est aussi trompeur.
Chaque appel en déclenche deux, et le compte explose : le sous-arbre grisé refait un calcul entièrement terminé ailleurs. Dès n = 5, la trace à la main devient impraticable.
Pas le bon modèle mental
Fibonacci est pratique pour montrer la syntaxe d'une méthode qui s'appelle elle-même. Mais il installe une mauvaise image : « une formule qui se rappelle deux fois », un tour de calcul à dérouler. Le modèle qui sert vraiment est structurel : un nœud fait son travail local, puis confie chaque sous-arbre au même code, et chaque sous-arbre n'est visité qu'une seule fois. C'est la zone suivante.
Les vrais modèles : parcourir et chercher
Le modèle structurel se décline en deux variantes, à connaître toutes les deux. printTree visite tout l'arbre et ne renvoie rien : l'appel seul suffit. onMenu cherche une étiquette et fait remonter sa réponse de cadre en cadre. Même arbre, même squelette.
Les niveaux du dessin deviennent l'indentation de la sortie : c'est depth qui fait le pont. Rien ne remonte : la méthode est void, chaque appel fait son affichage et c'est tout.
La forme du code épouse la forme de la donnée, et le squelette est le même des deux côtés. Seul change ce que chaque appel fait de ses enfants :
| printTree (void) | onMenu (boolean) | |
|---|---|---|
| Branche vide | return; | return false; |
| Travail local | Afficher l'étiquette, indentée selon depth. | Comparer l'étiquette à la cible. |
| Chaque enfant | Appel avec depth + 1. | Appel, arrêt au premier true. |
| Ce qui remonte | Rien : l'appel seul suffit. | Un boolean, relayé jusqu'au premier appel. |
Pourquoi deux méthodes pour printTree ?
L'appelant demande « affiche cet arbre » et fournit la racine, rien d'autre. La profondeur sert à l'implémentation, pas au contrat : la surcharge publique la fixe à 0 et la cache. Vous avez déjà vu ce découpage dans l'exercice de la leçon Arbres : contains(target) public, puis contains(node, target) privé. onMenu, elle, n'a pas besoin de surcharge : aucun paramètre technique ne voyage. Dès qu'une méthode récursive a besoin d'une information de plus (profondeur, chemin), ce duo est la forme à reproduire.
Le pari de la confiance
Pour écrire une méthode récursive, ne déroulez pas la pile dans votre tête. Faites le pari que l'appel récursif renvoie la bonne réponse pour le problème plus petit, puis vérifiez trois points, tous locaux.
Écrivez d'abord le cas de base
La plus petite entrée (null, 0, une liste vide) reçoit sa réponse directe, avant tout le reste.Écrivez l'appel réduit comme s'il marchait déjà
Supposez que l'appel sur le sous-problème renvoie la bonne réponse. Ne descendez pas vérifier.Combinez pour un seul nœud
Votre seule vraie responsabilité : que fait cet appel des réponses reçues ? Les additionne-t-il, les compare-t-il, les relaie-t-il ?
Relisez sumValues de la leçon Arbres avec ce pari : branche vide → 0 ; chaque enfant est un sous-arbre strictement plus petit ; la somme locale est juste si chaque enfant répond juste. Trois vérifications, zéro déroulé.
Quand parier
- • Écrire une méthode récursive.
- • Relire ou corriger du code récursif : les trois points suffisent.
- • Au besoin, tracer une seule petite entrée pour se rassurer, pas quinze.
Quand tracer à la main
- • Comprendre le mécanisme une première fois : c'est fait, plus haut.
- • Déboguer un cas précis qui échoue.
- • Dérouler une exécution précise pour l'expliquer : la zone d'entraînement arrive.
Tracer n'est pas interdit : c'est un autre outil, pour un autre moment. Écrire, c'est parier ; comprendre, déboguer et répondre à une question de trace, c'est tracer.
Quand ça tourne mal : lire le symptôme
Une récursivité cassée casse de trois façons, et chacune laisse un symptôme lisible dans la console. Savoir lire le symptôme, c'est savoir où regarder.
La pile continue de grandir
Premier appel
Java lève StackOverflowError quand la pile d'appels déborde. Le nom dit tout : la pile a débordé, la montée n'a jamais laissé place à la descente. badCountdown montre la variante sournoise : le cas de base existe, mais n saute par-dessus sans jamais l'atteindre.
| Symptôme | Cause probable | Où regarder |
|---|---|---|
StackOverflowError | Cas de base absent ou inatteignable, ou réduction qui ne réduit pas. | L'appel récursif : l'argument change-t-il ? Peut-il rater la condition d'arrêt ? |
NullPointerException | Le cas de base est testé après l'usage de la valeur. | L'ordre des premières lignes : node == null avant node.value. |
| Résultat faux, aucune erreur | Un résultat récursif calculé puis ignoré, ou une mauvaise combinaison. | Chaque appel récursif : est-il retourné, additionné, comparé ? |
Boucle ou récursivité ?
Après une leçon sur la récursivité, la tentation est de l'appliquer partout. Résistez : la récursivité n'est pas une boucle plus élégante. Elle convient bien aux données dont chaque partie reprend la même forme, comme les sous-arbres d'un arbre.
Les deux versions de sumTo sont correctes. Pour une suite plate, la boucle est plus simple à relire et n'empile aucun cadre. La version récursive était un exemple d'école, choisi pour sa petite taille, pas pour son bon goût.
| La donnée ressemble à… | Réflexe | Pourquoi |
|---|---|---|
| Une suite plate, parcourue du début à la fin (tableau, liste) | Boucle | Un curseur qui avance suffit ; aucun cadre à empiler. |
| Une structure dont chaque partie contient la même forme (arbre, dossiers, menus) | Récursivité | Chaque sous-partie est le même problème en plus petit ; la pile d'appels retient le chemin pour vous. |
| Une descente à une seule direction (recherche dirigée dans un BST) | Boucle ou récursivité | Les deux trouvent la valeur. Le while évite toutefois un cadre d'appel par niveau. |
Le bon réflexe
Une boucle simple et juste vaut toujours mieux qu'une récursivité élégante et fausse. Sur un arbre général, une boucle a besoin d'une pile explicite pour retenir les sous-arbres à visiter. La récursivité utilise la pile d'appels à cette fin, ce qui en fait souvent la forme la plus naturelle.
Entraînez-vous à la trace manuelle
Suivre une méthode récursive sur une structure donnée, papier au poing, est la meilleure preuve que le mécanisme est acquis. Travaillez le geste maintenant.
Cette méthode a deux cas de base : la branche vide répond 0, la feuille répond 1. C'est fréquent et parfaitement légal ; le test null reste en première ligne.
À vous, sur papier
Notez chaque appel dans l'ordre où il démarre, le cas atteint (branche vide, feuille ou nœud interne) et la valeur retournée. Repérez chaque appel par le nœud qu'il reçoit, par exemple node40 pour le nœud qui contient 40. Comptez le nombre total d'appels. Comparez ensuite seulement avec la correction ci-dessous.
La correction, dans l'ordre où les appels démarrent :
| Appel | Cas atteint | Retour |
|---|---|---|
countLeaves(node40) | nœud interne | 2 + 1 = 3 |
countLeaves(node20) | nœud interne | 1 + 1 = 2 |
countLeaves(node10) | feuille | 1 |
countLeaves(node30) | feuille | 1 |
countLeaves(node60) | nœud interne | 0 + 1 = 1 |
countLeaves(null) | branche vide | 0 |
countLeaves(node70) | feuille | 1 |
Remarquez que les feuilles node10, node30 et node70 ne lancent aucun appel sur leurs enfants : leur cas de base répond avant. Seul le côté gauche vide de node60 déclenche countLeaves(null). Et si votre trace n'avait qu'une seule variable node partagée entre les appels, relisez « Chaque appel a son propre monde ».
Vérifiez vos modèles mentaux
Vérifiez vos réflexes
Une réponse par question. La correction apparaît tout de suite.
Retour au parcours
La récursivité vit surtout dans la leçon Arbres : retournez-y écrire la recherche dirigée du BST, le pari de la confiance en tête. Et la pile d'appels que vous venez de tracer suit la même règle LIFO que la pile de la leçon Listes, piles et files.