Récursivité

Objectifs du chapitre

À la fin de ce chapitre, vous serez capable de:

• reconnaître une définition récursive, identifier son cas de base et son cas récursif, et expliquer pourquoi une fonction qui s'appelle elle-même n'est pas un raisonnement circulaire;
• décrire ce qui se passe dans la pile d'appels pendant une récursion, lire une trace de descente et de remontée, et interpréter un message RecursionError;
• écrire et comparer les versions récursive et itérative de la factorielle, de la somme d'une liste et de la recherche dichotomique;
• mesurer le nombre d'appels et le temps d'exécution d'une récursion, expliquer pourquoi la version naïve de Fibonacci est catastrophique, et la corriger par mémoïsation avec un dictionnaire;
• résoudre les tours de Hanoï récursivement et démontrer que la solution demande exactement 2ⁿ − 1 déplacements;
• choisir entre récursion et itération en connaissance de cause, en sachant que Python n'élimine pas les appels terminaux.

L'idée: une fonction qui s'appelle elle-même

Un problème que la boucle traite mal

Voici une poupée russe. Pour l'ouvrir entièrement, que faites-vous? Vous ouvrez la poupée, et si elle en contient une autre, vous ouvrez entièrement cette poupée-là. La description du travail contient le travail lui-même. Elle n'en est pas moins parfaitement exécutable, parce que chaque poupée intérieure est plus petite que celle qui la contenait, et qu'à la fin il y en a une qui ne contient rien.

Le même phénomène apparaît partout. Un dossier de votre ordinateur contient des fichiers et des dossiers, qui contiennent eux-mêmes des fichiers et des dossiers. Une phrase française contient des propositions, qui peuvent contenir des propositions. Le plan d'un livre a des parties, des chapitres, des sections, des sous-sections, et rien n'interdit d'aller plus loin. Chaque fois qu'un objet est défini en termes de lui-même en plus petit, une boucle for ou while devient un outil maladroit: elle sait répéter un traitement, mais pas s'enfoncer d'un niveau et revenir.

La récursivité est le nom de la technique qui exprime cela directement: une fonction dont le corps contient un appel à elle-même.

Écrivons la plus simple des fonctions récursives: un compte à rebours.

def compte_a_rebours(n):
    """Affiche n, n-1, ..., 1 puis Decollage."""
    if n == 0:                 # cas de base: rien a faire
        print("Decollage!")
    else:                      # cas recursif: probleme plus petit
        print(n)
        compte_a_rebours(n - 1)


compte_a_rebours(3)

3
2
1
Decollage!

Lisez le corps de la fonction sans chercher à «dérouler» quoi que ce soit dans votre tête. Il dit: compter à rebours depuis 0, c'est annoncer le décollage; compter à rebours depuis n, c'est afficher n puis compter à rebours depuis n − 1. Cette phrase est une définition complète du compte à rebours, et c'est exactement ce que le code exprime. Le programme fait quatre lignes, dont une seule dit quelque chose de nouveau.

«Mais c'est circulaire!»

L'objection vient immédiatement, et il faut la prendre au sérieux plutôt que la balayer: comment une fonction peut-elle s'utiliser elle-même alors qu'elle n'est pas encore terminée? Si je définis «un homme sage est un homme sage», je n'ai rien défini du tout.

La réponse tient en une phrase: l'appel récursif ne porte pas sur le même problème. compte_a_rebours(3) n'appelle pas compte_a_rebours(3), il appelle compte_a_rebours(2). La fonction ne s'utilise pas elle-même, elle utilise son résultat sur un cas plus petit. Et comme ce cas plus petit est lui-même traité en descendant encore d'un cran, on obtient une suite strictement décroissante d'entiers positifs: 3, 2, 1, 0. Une telle suite ne peut pas être infinie. Elle atteint nécessairement le cas de base, où la descente s'arrête.

C'est très exactement le raisonnement par récurrence des mathématiques, retourné. Une démonstration par récurrence établit une propriété pour $n=0$, puis l'établit pour $n$ en la supposant vraie pour $n-1$. Une fonction récursive calcule le résultat pour $n=0$ directement, puis calcule le résultat pour $n$ en utilisant celui pour $n-1$. La récurrence est une preuve qui descend; la récursion est un calcul qui descend.

Il y a donc trois questions à se poser devant toute fonction récursive, et elles constituent votre méthode de relecture pour tout le chapitre:

1. Quel est le cas de base? Existe-t-il, et est-il atteint?
2. Le cas récursif diminue-t-il le problème? De combien, et selon quelle mesure (un entier, la longueur d'une liste, la taille d'un intervalle)?
3. Si je suppose que l'appel récursif est correct, le cas récursif l'est-il aussi? C'est le pas de récurrence, et c'est la seule chose à vérifier: il est inutile, et même contre-productif, de tenter de dérouler mentalement les cinquante appels.

Cette troisième question est le vrai changement d'habitude que ce chapitre demande. Devant un while, on raisonne sur l'état des variables tour après tour. Devant une récursion, on fait confiance à l'appel récursif — c'est ce qu'on appelle parfois le «saut de foi récursif» — et on vérifie seulement qu'on assemble correctement son résultat. Le reste est garanti par la décroissance et le cas de base.

Cas de base et cas récursif

Les deux ingrédients

Toute fonction récursive se compose de deux parties, et il est utile de prendre l'habitude de les écrire dans cet ordre:

• le cas de base, qui donne la réponse directement, sans appel récursif. Il correspond au problème le plus petit possible: l'entier 0, la liste vide, la chaîne d'un seul caractère, l'intervalle de recherche vide;
• le cas récursif, qui exprime la réponse pour le problème courant en fonction de la réponse pour un problème plus petit, obtenue par un appel récursif.

Le cas de base n'est pas une formalité administrative: c'est lui qui rend le calcul possible. Sans lui, il n'y a pas de calcul du tout, seulement une promesse infinie.

Ce qui arrive quand le cas de base manque

Le meilleur moyen de s'en convaincre est de l'enlever. Reprenons le compte à rebours sans son if:

def compte_sans_base(n):
    print(n)
    compte_sans_base(n - 1)


compte_sans_base(3)

Le programme affiche d'abord ce qu'on attend, puis continue là où il ne devrait pas:

3
2
1
0
-1
-2
-3
...
-995

Il imprime 999 nombres, de 3 jusqu'à −995, puis s'arrête sur une erreur. Voici le début et la fin du message, tel que Python 3.13 l'a produit (le chemin du fichier dépend de l'endroit où vous l'avez enregistré; il est raccourci ici en compte.py):

Traceback (most recent call last):
  File "compte.py", line 6, in <module>
    compte_sans_base(3)
    ~~~~~~~~~~~~~~~~^^^
  File "compte.py", line 3, in compte_sans_base
    compte_sans_base(n - 1)
    ~~~~~~~~~~~~~~~~^^^^^^^
  File "compte.py", line 3, in compte_sans_base
    compte_sans_base(n - 1)
    ~~~~~~~~~~~~~~~~^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Lisons ce message ligne par ligne, comme au chapitre 1.

• Traceback (most recent call last): Python annonce la liste des appels en cours au moment de l'erreur, du plus ancien au plus récent. Le dernier bloc affiché est donc celui où l'erreur s'est produite.
• La première entrée, line 6, in <module>, est l'appel que vous avez écrit vous-même: compte_sans_base(3). <module> désigne le corps du fichier, hors de toute fonction.
• Les entrées suivantes, toutes identiques, sont les appels que la fonction s'est faits. Python en affiche quelques-unes, puis résume: [Previous line repeated 996 more times] — la même ligne encore 996 fois. Cette ligne est la signature visuelle d'une récursion infinie: quand vous la voyez, cherchez un cas de base manquant.
• La dernière ligne donne le type de l'erreur et son message: RecursionError: maximum recursion depth exceeded, «profondeur maximale de récursion dépassée».

Notez ce que Python ne fait pas: il ne tourne pas indéfiniment. Il compte les appels imbriqués et refuse d'aller au-delà d'une limite.

La limite de récursion

Cette limite est une valeur que vous pouvez consulter dans le module sys (chapitre 8):

import sys

print(sys.getrecursionlimit())

1000

Mille appels imbriqués au maximum, donc — dans une installation standard de CPython. Ce nombre n'a rien de mathématique: c'est un garde-fou choisi par les auteurs de Python. Chaque appel de fonction consomme une zone de mémoire (nous verrons laquelle à la section suivante), et cette mémoire n'est pas extensible à volonté; sans limite, une récursion infinie ferait tomber tout l'interpréteur au lieu de lever une erreur propre que votre programme peut attraper avec try / except (chapitre 8).

Le compte des 999 nombres affichés s'explique alors exactement: le corps du fichier occupe déjà un niveau, et il reste 999 niveaux pour la fonction. La limite est atteinte au 1000ᵉ.

La pile d'appels

Cette section est le cœur conceptuel du chapitre. Tout ce qui précède décrivait la récursion comme une définition; il faut maintenant comprendre ce que la machine fait, car c'est cela qui explique la limite de 1000, le RecursionError, le coût d'un appel et l'ordre déroutant dans lequel les résultats reviennent.

Un cadre par appel

Quand Python exécute un appel de fonction — récursif ou non —, il crée une zone de mémoire appelée cadre d'appel.

Trois conséquences immédiates, qu'il faut retenir:

• Chaque appel a ses propres variables. Les cinq appels de factorielle que nous allons suivre ont chacun leur n; ils ne se marchent pas dessus. C'est la portée locale du chapitre 4, appliquée cinq fois à la même fonction.
• Un appel est suspendu, pas abandonné. Quand factorielle(4) appelle factorielle(3), le cadre de factorielle(4) reste en mémoire, avec son n valant 4 et la multiplication qui l'attend. Il reprendra exactement là où il s'était arrêté.
• La pile a une taille finie. C'est elle que la limite de 1000 protège.

Descente et remontée sur un exemple

Instrumentons une factorielle pour qu'elle raconte ce qu'elle fait. La variable profondeur ne sert qu'à décaler l'affichage: elle n'intervient pas dans le calcul.

def factorielle(n, profondeur=0):
    marge = "  " * profondeur
    print(f"{marge}-> factorielle({n})")
    if n == 0:
        resultat = 1
    else:
        resultat = n * factorielle(n - 1, profondeur + 1)

-> factorielle(4)
  -> factorielle(3)
    -> factorielle(2)
      -> factorielle(1)
        -> factorielle(0)
        <- factorielle(0) retourne 1
      <- factorielle(1) retourne 1
    <- factorielle(2) retourne 2
  <- factorielle(3) retourne 6
<- factorielle(4) retourne 24

Regardez la forme de cette trace: un V couché. La moitié supérieure est la descente, cinq appels qui s'empilent sans qu'aucun ne produise encore de valeur. Puis le cas de base est atteint et rien ne descend plus. La moitié inférieure est la remontée (unwinding), cinq retours qui dépilent les cadres dans l'ordre inverse de leur création.

Deux détails méritent qu'on s'y arrête.

D'abord, le premier appel est le dernier à retourner. factorielle(4) est la première ligne affichée et la dernière: elle attend pendant toute la durée du calcul. C'est la propriété fondamentale d'une pile — dernier entré, premier sorti — et c'est elle qui rend la trace lisible une fois qu'on l'a comprise.

Ensuite, rien n'est calculé pendant la descente. Aucune multiplication n'a lieu avant que factorielle(0) ne retourne 1. Les quatre multiplications se font toutes pendant la remontée: 1 × 1, puis 2 × 1, puis 3 × 2, puis 4 × 6. La descente ne fait que poser des questions; la remontée y répond.

La figure 9.1 dessine la même chose que la trace, mais en insistant sur la mémoire. Les cinq cadres coexistent au moment où le cas de base est atteint: à cet instant précis, cinq copies de la variable n existent simultanément, valant 4, 3, 2, 1 et 0. Mesurons cette profondeur plutôt que de l'affirmer:

plus_profond = 0


def factorielle(n, profondeur=1):
    global plus_profond
    if profondeur > plus_profond:
        plus_profond = profondeur
    if n == 0:
        return 1
    return n * factorielle(n - 1, profondeur + 1)


for n in [4, 

factorielle(4) : profondeur maximale = 5
factorielle(10) : profondeur maximale = 11
factorielle(100) : profondeur maximale = 101

La profondeur vaut $n+1$: le cas de base compte pour un cadre. Avec la limite de 1000, factorielle cesse donc de fonctionner au-delà de $n=998$ — valeur mesurée en la lançant — non parce que le résultat serait trop grand (les entiers de Python n'ont pas de limite de taille), mais parce que la pile, elle, en a une.

La factorielle, de bout en bout

La définition

La factorielle d'un entier $n\ge 0$ est le produit des entiers de 1 à $n$, avec la convention $0!=1$. Elle compte le nombre de façons d'ordonner $n$ objets: il y a $4!=24$ manières de ranger quatre livres sur une étagère.

Cette définition «produit des entiers de 1 à n» appelle naturellement une boucle. Mais la factorielle possède une seconde définition, équivalente et récursive:

La relation (9.1) est littéralement un cas de base et un cas récursif. La traduire en Python ne demande aucun travail:

def factorielle(n):
    """Retourne n! pour un entier n >= 0."""
    if n == 0:              # cas de base: 0! vaut 1
        return 1
    return n * factorielle(n - 1)   # cas recursif


print(factorielle(4))
print(factorielle(0))
print(factorielle(20))

24
1
2432902008176640000

Vérifions les trois questions de méthode. Cas de base: n == 0, il retourne 1 sans appel. Décroissance: l'appel porte sur n - 1, et partant d'un entier positif on atteint 0 en exactement $n$ étapes. Correction du cas récursif: si factorielle(n - 1) retourne bien $(n-1)!$, alors n * factorielle(n - 1) vaut $n\times (n-1)!=n!$ par (9.1). Les trois réponses sont satisfaisantes, la fonction est correcte. Nous n'avons déroulé aucun appel.

La version itérative

La même fonction s'écrit avec une boucle, comme au chapitre 3: un accumulateur initialisé à 1, multiplié par chaque facteur.

def factorielle_iterative(n):
    """Meme resultat, sans appel recursif."""
    resultat = 1
    for facteur in range(2, n + 1):
        resultat = resultat * facteur
    return resultat


print(factorielle_iterative(4))
print(factorielle_iterative(0))
print(factorielle_iterative(20))

24
1
2432902008176640000

Les deux versions donnent les mêmes valeurs. Comparons-les honnêtement.

Le temps d'exécution suit la mémoire. Mesurons-le en appelant chaque version cent mille fois:

import time

# Les deux fonctions sont celles definies ci-dessus.
for fonction in [factorielle, factorielle_iterative]:
    debut = time.perf_counter()
    for _ in range(100000):
        fonction(20)
    duree = time.perf_counter() - debut
    print(f"{fonction.__name__:22s} {duree:.3f} s pour 100000 appels")

factorielle            0.110 s pour 100000 appels
factorielle_iterative  0.054 s pour 100000 appels

Ces durées dépendent de la machine, de la version de Python et de ce qui tourne à côté: relancez le programme, vous obtiendrez des valeurs différentes, et sur un autre ordinateur elles peuvent être doubles ou moitié. Sur la machine qui a servi ici, dix exécutions successives ont donné entre 0,10 et 0,19 s pour la version récursive et entre 0,05 et 0,07 s pour l'itérative, selon la charge de l'ordinateur. Ce qui survit à cette dispersion, c'est le rapport: la version récursive est de deux à trois fois plus lente, parce que créer et détruire un cadre d'appel coûte nettement plus cher qu'un tour de boucle. Retenez l'ordre de grandeur, pas les chiffres.

Pour la factorielle, l'itération gagne donc sur tous les tableaux sauf un: la lisibilité de la version récursive, qui est la traduction mot à mot de la définition mathématique. C'est un cas où la récursion est un bon outil pédagogique et un mauvais choix d'implémentation. Il y a des problèmes où c'est l'inverse, et nous allons en voir.

Fibonacci, ou le prix d'une belle définition

La suite et sa traduction naïve

La suite de Fibonacci est définie par

Elle commence par 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. Comme (9.1), la relation (9.2) est faite de cas de base — il y en a deux ici — et d'un cas récursif. La traduction est encore plus directe que pour la factorielle:

def fibonacci(n):
    """Version naive: 2 appels recursifs par appel."""
    if n <= 1:          # cas de base: fib(0) = 0, fib(1) = 1
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

Trois lignes, parfaitement correctes, et une élégance qui a fait la fortune de cet exemple dans tous les manuels. Cette fonction est pourtant l'un des pires programmes qu'on puisse écrire, et il est essentiel de comprendre pourquoi: c'est la leçon la plus utile du chapitre.

Compter les appels

N'affirmons rien: comptons. Une variable globale incrémentée à chaque entrée dans la fonction suffit (le mot-clé global, vu au chapitre 4, autorise la fonction à modifier une variable du module).

appels = 0


def fibonacci(n):
    global appels
    appels += 1
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)


for n in [5, 10, 20, 25, 30]:

n =  5  fib =      5  appels = 15
n = 10  fib =     55  appels = 177
n = 20  fib =   6765  appels = 21891
n = 25  fib =  75025  appels = 242785
n = 30  fib = 832040  appels = 2692537

Lisez la dernière ligne lentement. Pour obtenir le nombre 832 040, Python a effectué 2 692 537 appels de fonction. Il a créé et détruit deux millions et demi de cadres pour produire un entier de six chiffres. Entre $n=25$ et $n=30$, cinq unités de plus, le nombre d'appels a été multiplié par 11.

Le motif est facile à formuler. Notons $a_n$ le nombre d'appels engendrés par fibonacci(n). On a $a_0=a_1=1$, et pour $n\ge 2$, l'appel lui-même plus ceux de ses deux sous-appels:

C'est presque la relation de Fibonacci elle-même: on démontre sans peine que $a_n=2F_{n+1}-1$. Le nombre d'appels croît donc comme la suite de Fibonacci, c'est-à-dire exponentiellement, à peu près comme $1,618^n$. Chaque unité ajoutée à $n$ multiplie le travail par 1,6 environ.

Mesurer le temps

import time


def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)


for n in [20, 25, 30, 32, 35]:
    debut = time.perf_counter()
    valeur = fibonacci(n)

n = 20  fib =     6765  duree =    0.001 s
n = 25  fib =    75025  duree =    0.010 s
n = 30  fib =   832040  duree =    0.117 s
n = 32  fib =  2178309  duree =    0.312 s
n = 35  fib =  9227465  duree =    1.838 s

Mesures faites sur un ordinateur portable ordinaire avec Python 3.13; encore une fois, les durées absolues dépendent de la machine, mais leur progression ne dépend que de l'algorithme. De $n=25$ à $n=30$, le temps est multiplié par 11,7; de 30 à 35, par 15,7. Prolongeons d'un cran: sur la même machine, fibonacci(40) a demandé 21,2 secondes pour retourner 102 334 155. Encore cinq unités et l'on dépasserait les quatre minutes; à $n=60$, il faudrait attendre des semaines. Pour une suite dont un élève calcule le soixantième terme en quelques minutes avec un papier et un crayon.

Pourquoi: l'arbre des appels

La cause n'est pas mystérieuse, et elle se voit d'un coup d'œil sur l'arbre des appels.

fibonacci(5) appelle fibonacci(4) et fibonacci(3). Mais fibonacci(4) appelle à son tour fibonacci(3): le même calcul est donc lancé deux fois, intégralement, sans que l'un profite de l'autre. Et la duplication se reproduit à chaque niveau. Sur la figure 9.2, fib(3) apparaît 2 fois, fib(2) 3 fois, fib(1) 5 fois et fib(0) 3 fois: quinze appels pour seulement six valeurs distinctes. Le programme ne calcule pas une suite, il redécouvre chaque terme un nombre exponentiel de fois.

La récursion n'est pas coupable. La faute est de ne garder aucune trace des résultats déjà obtenus.

La mémoïsation

Le remède tient en une idée: retenir ce qu'on a déjà calculé. On se munit d'un dictionnaire (chapitre 7) qui associe à chaque n la valeur $F_n$ trouvée. Avant de calculer, on regarde si la réponse y est déjà; après avoir calculé, on l'y range.

def fibonacci_memo(n, connus=None):
    """Avec memoire: chaque valeur n'est calculee qu'une fois."""
    if connus is None:
        connus = {}
    if n <= 1:
        return n
    if n in connus:           # deja calcule: on le relit
        return connus[n]
    gauche = fibonacci_memo(n - 1, connus)
    droite = fibonacci_memo(n - 2, connus)

832040
102334155
2880067194370816120

Le if connus is None: connus = {} mérite une explication. On aimerait écrire def fibonacci_memo(n, connus={}), mais c'est le piège de l'argument par défaut mutable rencontré au chapitre 4: la valeur par défaut est créée une seule fois, à la définition de la fonction, et serait partagée par tous les appels ultérieurs du programme. Ici, cela «marcherait» même mieux (le cache survivrait d'un appel à l'autre), mais la fonction cesserait d'être prévisible, et la même construction sur une liste produit des bogues redoutables. Le None est l'idiome correct: un dictionnaire neuf par appel extérieur, transmis ensuite à tous les appels récursifs.

Mesurons le gain, appels et temps:

appels = 0


def fibonacci_memo(n, connus=None):
    global appels
    appels += 1
    if connus is None:
        connus = {}
    if n <= 1:
        return n
    if n in connus:
        return connus[n]
    gauche = fibonacci_memo(n - 1, connus)

et la boucle de mesure elle-même:

import time

for n in [5, 10, 20, 30, 35]:
    appels = 0
    debut = time.perf_counter()
    valeur = fibonacci_memo(n)
    duree = (time.perf_counter() - debut) * 1e6
    ligne = f"n = {n:2d}  fib = {valeur:8d

n =  5  fib =        5  appels =   9  duree =      3.4 us
n = 10  fib =       55  appels =  19  duree =      2.8 us
n = 20  fib =     6765  appels =  39  duree =      5.0 us
n = 30  fib =   832040  appels =  59  duree =      6.5 us
n = 35  fib =  9227465  appels =  69  duree =      7.1 us

Le nombre d'appels vaut exactement $2n-1$: il est linéaire, alors qu'il était exponentiel. Mettons les deux colonnes côte à côte pour $n=35$:

Le même algorithme, la même définition récursive, quelques lignes ajoutées, et un facteur de l'ordre de deux cent mille. Et ce facteur n'est pas constant: il croît avec $n$, puisque l'une des deux versions est exponentielle et l'autre linéaire. À $n=40$, la version naïve demande 21 secondes et la mémoïsée reste sous les dix microsecondes.

Les tours de Hanoï

Le problème

Trois tiges, notées A, B et C. Sur la tige A, $n$ disques de diamètres tous différents, empilés du plus grand en bas au plus petit en haut. Il s'agit de transporter toute la pile sur la tige C en respectant deux règles: on ne déplace qu'un disque à la fois, en le prenant au sommet d'une tige, et on ne pose jamais un disque sur un disque plus petit.

C'est un casse-tête vendu dans les magasins de jouets, inventé en 1883 par le mathématicien français Édouard Lucas et accompagné d'une légende: des moines d'un temple de Bénarès déplaceraient ainsi 64 disques d'or, et le monde finirait à leur dernier coup. Nous verrons que la légende est bien calibrée.

Essayez à quatre disques avec des pièces de monnaie: c'est étonnamment difficile. Essayez de décrire la méthode que vous employez: c'est presque impossible. Il n'existe pas de description itérative simple de la solution — et pourtant la solution récursive tient en cinq lignes.

L'idée récursive

Supposez le problème résolu pour $n-1$ disques — le saut de foi récursif. Pour déplacer $n$ disques de A vers C:

1. déplacer les $n-1$ disques du dessus de A vers B, en se servant de C comme tige libre. Le grand disque, tout en bas, ne gêne personne: il est plus grand que tous les autres, donc n'importe quel disque peut lui être posé dessus, et il est comme absent pendant cette étape;
2. déplacer le grand disque de A vers C. Un seul mouvement, et il est légal puisque C est vide;
3. déplacer les $n-1$ disques de B vers C, en se servant de A comme tige libre. Ils arrivent sur le grand disque, qui est plus grand qu'eux: légal.

Le cas de base est $n=0$: aucun disque, rien à faire.

Remarquez que les trois tiges ne jouent pas un rôle fixe: à chaque étape, l'une est le départ, l'une l'arrivée et l'une l'intermédiaire, et ces rôles tournent. C'est la raison pour laquelle la fonction prend les trois noms en paramètres.

def hanoi(n, depart, arrivee, intermediaire):
    """Deplace n disques de depart vers arrivee, via intermediaire."""
    if n == 0:                                    # rien a deplacer
        return
    hanoi(n - 1, depart, intermediaire, arrivee)  # la tour s'ecarte
    print(f"disque {n}: {depart} -> {arrivee}")   # le grand disque
    hanoi(n - 1, intermediaire, arrivee, depart)  # la tour revient


hanoi(

disque 1: A -> C
disque 2: A -> B
disque 1: C -> B
disque 3: A -> C
disque 1: B -> A
disque 2: B -> C
disque 1: A -> C

Sept déplacements pour trois disques. Observez la structure de la liste: les trois premiers déplacements transportent la tour de deux disques de A vers B, le quatrième déplace le grand disque de A vers C, et les trois derniers ramènent la tour de deux disques de B vers C. Les trois étapes du raisonnement sont visibles telles quelles dans la sortie.

Combien de déplacements?

Démonstration. Notons $d_n$ le nombre de déplacements effectués par hanoi(n, ...). Le cas de base ne déplace rien: $d_0=0$. Pour $n\ge 1$, la fonction effectue deux fois le travail pour $n-1$ disques, plus un déplacement:

Montrons (9.4) par récurrence. Pour $n=0$: $2^0-1=0=d_0$. Supposons $d_{n-1}=2^{n-1}-1$; alors

ce qui établit la formule pour tout $n\ge 0$. Quant à la profondeur, chaque appel n'a qu'un seul appel en cours à la fois (le premier sous-appel est terminé avant que le second ne commence), donc la pile contient au plus un cadre par valeur de $n$ de $n$ à 0, soit $n+1$ cadres. $\square$

La démonstration est courte, mais ne nous en contentons pas: le chapitre exige que les nombres soient mesurés. Remplaçons le print par un compteur et comparons avec la formule.

deplacements = 0


def hanoi(n, depart, arrivee, intermediaire):
    global deplacements
    if n == 0:
        return
    hanoi(n - 1, depart, intermediaire, arrivee)
    deplacements += 1
    hanoi(n - 1, intermediaire, arrivee, depart)


for n in range(1, 11):
    deplacements = 0
    hanoi(n, "A"

n =  1  deplacements =    1  2**n - 1 =    1
n =  2  deplacements =    3  2**n - 1 =    3
n =  3  deplacements =    7  2**n - 1 =    7
n =  4  deplacements =   15  2**n - 1 =   15
n =  5  deplacements =   31  2**n - 1 =   31
n =  6  deplacements =   63  2**n - 1 =   63
n =  7  deplacements =  127  2**n - 1 =  127
n =  8  deplacements =  255  2**n - 1 =  255
n =  9  deplacements =  511  2**n - 1 =  511
n = 10  deplacements = 1023  2**n - 1 = 1023

Les deux colonnes coïncident sur les dix premières valeurs: la formule et le programme disent la même chose. On peut aussi démontrer — c'est plus difficile, et nous ne le ferons pas ici — qu'aucune solution ne fait mieux: $2^n-1$ est le nombre minimal de déplacements. La légende de Bénarès est donc quantifiable: $2^{64}-1\approx 1,8\times 10^{19}$ déplacements, soit à raison d'un déplacement par seconde, près de 585 milliards d'années. Il reste du temps.

Voir le coût varier

L'explorateur ci-dessous met les trois récursions du chapitre sur le même graphique, en échelle logarithmique. Déplacez le curseur n et comparez les trois lectures: le nombre d'appels, la profondeur maximale de la pile et le résultat.

Deux observations à faire soi-même. D'abord, la profondeur reste sage dans les trois cas: elle vaut $n+1$ pour la factorielle et pour Hanoï, et $n$ pour Fibonacci. Ce n'est jamais la profondeur qui explose. Ensuite, le nombre d'appels sépare radicalement la factorielle des deux autres: 21 appels pour factorielle(20), 21 891 pour fibonacci(20), plus de deux millions pour hanoi(20). En échelle logarithmique, une courbe qui monte en ligne droite est une exponentielle; la factorielle, elle, reste presque plate.

D'autres récursions naturelles

La factorielle et Fibonacci sont des exemples d'école. Voici cinq récursions que l'on écrit vraiment, et qui montrent que la «taille» qui décroît peut être bien autre chose qu'un entier.

Sur la longueur d'une liste

La somme d'une liste vide vaut 0; la somme d'une liste non vide vaut son premier élément plus la somme du reste. La tranche liste[1:] (chapitre 6) est exactement «le reste».

def somme(liste):
    """Somme des elements d'une liste, par recursion."""
    if len(liste) == 0:          # cas de base: la liste vide
        return 0
    return liste[0] + somme(liste[1:])   # premier + somme du reste


notes = [4.5, 5.0, 3.5, 6.0, 4.0, 5.5, 4.5, 3.0, 5.0, 

45.5
4.55
0

On retrouve les faits du carnet de notes du cours: une somme de 45,5 et une moyenne de 4,55 sur dix élèves. La grandeur qui décroît est ici la longueur de la liste, qui diminue de 1 à chaque appel.

Cette version a un défaut caché, instructif: liste[1:] copie la fin de la liste à chaque appel. Pour dix notes c'est sans importance; pour une liste de cent mille éléments, on copierait cent mille listes, et la fonction serait de toute façon arrêtée bien avant par la limite de récursion. Une somme sur une longue liste s'écrit avec une boucle, ou avec la fonction native sum.

Sur une chaîne de caractères

Inverser une chaîne se dit récursivement: l'inverse d'une chaîne d'au plus un caractère est elle-même; l'inverse d'une chaîne plus longue est l'inverse de sa fin, suivi de son premier caractère.

def inverse(chaine):
    """Retourne la chaine lue a l'envers."""
    if len(chaine) <= 1:              # cas de base: 0 ou 1 caractere
        return chaine
    return inverse(chaine[1:]) + chaine[0]   # le reste, puis le 1er


print(inverse("recursivite"))
print(inverse("ressasser"))

etivisrucer
ressasser

Le second mot est un palindrome, ce qui se voit: son inverse lui est identique. On peut d'ailleurs tester la propriété directement, et le faire en réduisant le problème par les deux bouts à la fois: la taille diminue alors de 2 par appel.

def est_palindrome(chaine):
    """Vrai si la chaine se lit pareil dans les deux sens."""
    if len(chaine) <= 1:                   # 0 ou 1 caractere
        return True
    if chaine[0] != chaine[-1]:            # extremites differentes
        return False
    return est_palindrome(chaine[1:-1])    # on enleve les deux bouts


for mot in ["ressasser", "kayak", 

ressasser  True
kayak      True
python     False
a          True

Cette fonction possède deux cas de base: la chaîne trop courte, qui vaut True, et la découverte d'extrémités différentes, qui vaut False sans aucun appel récursif. Avoir plusieurs cas de base est parfaitement normal; ce qui compte est qu'ils couvrent tous les arrêts possibles. Notez aussi qu'un cas de base peut être un échec: on arrête la descente dès qu'on sait répondre.

Sur un intervalle qu'on coupe en deux

La recherche dichotomique sur un tableau trié est la récursion la plus utile du chapitre. Pour chercher une valeur dans tableau[gauche:droite+1], on regarde l'élément du milieu: s'il est égal à la cible, c'est fini; s'il est plus petit, la cible ne peut être que dans la moitié droite; s'il est plus grand, dans la moitié gauche. À chaque appel, l'intervalle est divisé par deux.

def recherche(tableau, cible, gauche, droite):
    """Indice de cible entre gauche et droite inclus, sinon -1."""
    if gauche > droite:              # cas de base: intervalle vide
        return -1
    milieu = (gauche + droite) // 2
    if tableau[milieu] == cible:
        return milieu
    if tableau[milieu] < cible:      # la cible est a droite
        return recherche(tableau, cible, milieu + 1, droite)
    return recherche(tableau, cible, gauche, milieu - 1

3 0
27 3
82 6
40 -1

Ajoutons un print pour voir les intervalles successifs dans le cas de la cible 43:

gauche=0 droite=6 milieu=3 valeur=27
gauche=4 droite=6 milieu=5 valeur=43
indice trouve: 5

Deux comparaisons pour trouver 43 dans sept éléments, là où un parcours séquentiel en aurait fait six. La grandeur qui décroît, ici, est la largeur de l'intervalle, et elle est divisée par deux à chaque appel plutôt que diminuée de 1: la descente est donc très courte. Le chapitre 10 mesurera précisément ce que cela coûte et pourquoi c'est le bon algorithme dès que le tableau est grand.

Sur une structure emboîtée

Voici enfin le cas où la récursion ne remplace aucune boucle: celui où la donnée elle-même est emboîtée. Représentons une arborescence de dossiers par des dictionnaires (chapitre 7): une clé est un nom, la valeur est soit un entier — la taille d'un fichier en kilo-octets — soit un autre dictionnaire, c'est-à-dire un sous-dossier. Rien ne fixe la profondeur à l'avance; c'est précisément le point.

# Un dossier est un dictionnaire; un fichier, sa taille en Ko.
cours = {
    "notes.txt": 3,
    "images": {"schema.png": 120, "photo.jpg": 480},
    "code": {
        "tri.py": 2,
        "tests": {"test_tri.py": 1, "donnees.csv": 15},
    },
}

La fonction qui totalise les tailles parcourt les entrées d'un dossier et, chaque fois qu'une entrée est elle-même un dossier, se rappelle sur lui:

def taille_totale(dossier):
    """Somme des tailles de tous les fichiers, a tout niveau."""
    total = 0
    for contenu in dossier.values():
        if isinstance(contenu, dict):     # un sous-dossier
            total = total + taille_totale(contenu)
        else:                             # un fichier
            total = total + contenu
    return total


print(taille_totale(cours))
print(taille_totale(cours["code"]))

621
18

Vérification à la main: 3 + 120 + 480 + 2 + 1 + 15 = 621, et pour le sous-dossier code, 2 + 1 + 15 = 18. La fonction native isinstance(objet, dict) répond «cet objet est-il un dictionnaire?», c'est-à-dire ici «est-ce un dossier plutôt qu'un fichier?».

Cette fonction mêle boucle et récursion, et c'est normal: la boucle parcourt les entrées d'un même dossier, la récursion descend d'un niveau. Le cas de base n'est pas écrit explicitement — il est atteint dès qu'un dossier ne contient que des fichiers, car alors aucun appel récursif n'a lieu; un dossier vide fait retourner 0 sans rien parcourir. La profondeur des appels est celle de l'arborescence, pas le nombre de fichiers.

Le même schéma affiche l'arborescence, en utilisant la profondeur pour l'indentation:

def afficher(dossier, profondeur=0):
    """Affiche l'arborescence, indentee par niveau de recursion."""
    for nom, contenu in dossier.items():
        marge = "    " * profondeur
        if isinstance(contenu, dict):
            print(f"{marge}{nom}/")
            afficher(contenu, profondeur + 1)
        else:
            print(f

notes.txt  (3 Ko)
images/
    schema.png  (120 Ko)
    photo.jpg  (480 Ko)
code/
    tri.py  (2 Ko)
    tests/
        test_tri.py  (1 Ko)
        donnees.csv  (15 Ko)

Essayez d'écrire cette fonction avec une boucle while et sans récursion: c'est faisable, mais il vous faudra gérer vous-même une liste des dossiers restant à visiter — c'est-à-dire réimplémenter une pile à la main. La récursion vous offre celle de Python gratuitement.

Récursion contre itération

Elles ont la même puissance

Commençons par le fait théorique, qui rassure: toute fonction récursive peut s'écrire de façon itérative, et réciproquement. On l'a vu pour la factorielle; c'est vrai en général, quitte à gérer soi-même une pile explicite comme l'exemple des dossiers le suggérait. Le choix entre les deux n'est donc jamais une question de possibilité, seulement d'opportunité. Trois critères comptent.

La lisibilité. Quand la définition du problème est elle-même récursive — une relation de récurrence, une structure emboîtée, un «diviser pour régner» —, la version récursive est plus courte, plus proche de l'énoncé, et plus facile à croire correcte. hanoi en est la démonstration: cinq lignes contre une machinerie itérative que personne n'écrit spontanément. Quand le problème est un simple parcours — additionner des nombres, compter des caractères, lire un fichier ligne par ligne —, la boucle est plus claire et la récursion fait de l'esbroufe.

Le coût. Un appel de fonction coûte plus cher qu'un tour de boucle: il faut créer un cadre, y copier les arguments, et le détruire au retour. Notre mesure sur la factorielle donnait un rapport de deux à trois. Ce n'est pas rédhibitoire, mais c'est réel, et cela s'ajoute au coût de l'algorithme lui-même. Attention toutefois: ce facteur constant est presque toujours négligeable devant une erreur d'algorithme. La version naïve de Fibonacci n'est pas lente parce qu'elle est récursive; elle est lente parce qu'elle recalcule. La version mémoïsée, tout aussi récursive, est instantanée.

La profondeur de pile. C'est la contrainte dure. Une récursion dont la profondeur croît comme $n$ est plafonnée à environ mille par la limite de CPython. Une boucle, elle, peut tourner un milliard de fois sans consommer un octet de plus.

def somme_jusqua(n):
    """1 + 2 + ... + n, par recursion."""
    if n == 0:
        return 0
    return n + somme_jusqua(n - 1)


print(somme_jusqua(100))
print(somme_jusqua(900))
print(somme_jusqua(2000))

5050
405450

puis, sur la troisième ligne:

RecursionError: maximum recursion depth exceeded

La fonction est correcte. Elle marche pour $n=900$ et échoue pour $n=2000$, non par un défaut de logique mais parce que la machine manque de place. La même somme écrite avec un for fonctionne pour $n=10^7$ sans sourciller. Retenez la règle pratique: une récursion dont la profondeur est proportionnelle à la taille des données est un mauvais choix en Python; une récursion dont la profondeur est logarithmique (dichotomie: 20 niveaux pour un million d'éléments) ou bornée par la profondeur d'une structure (une arborescence de fichiers dépasse rarement 30 niveaux) ne pose aucun problème.

Pourquoi Python ne sauve pas les appels terminaux

Regardez de près la dernière ligne de somme_jusqua: return n + somme_jusqua(n - 1). Après le retour de l'appel récursif, il reste une addition à faire; le cadre doit donc être conservé. Mais dans hanoi, le second appel récursif est la toute dernière chose que la fonction fait: rien ne l'attend au retour.

Python ne le fait pas. C'est une décision explicite de Guido van Rossum, son créateur, et elle a deux motifs assumés: préserver des traces d'erreur complètes — vous avez vu au début du chapitre combien la pile affichée est informative —, et ne pas faire dépendre la validité d'un programme d'une optimisation invisible dans le code.

Les conséquences sont pratiques et il faut les connaître:

• réécrire une fonction pour rendre sa récursion terminale ne sert à rien en Python. La classique factorielle «à accumulateur», def fact(n, acc=1): return acc if n == 0 else fact(n - 1, acc * n), est terminale — et lève exactement le même RecursionError que l'autre;
• la limite de 1000 s'applique donc à toutes les récursions, terminales ou non;
• un code trouvé dans un manuel de Scheme ou d'OCaml, où une récursion profonde de un million est idiomatique, ne se transpose pas tel quel;
• quand une récursion est terminale, en revanche, elle se convertit en boucle de façon mécanique et sans ruse: le paramètre qui change devient une variable, et l'appel devient un tour de boucle. C'est la bonne réaction devant un RecursionError sur une récursion terminale.

La règle du pouce

En Python, et pour un premier cours:

• choisissez la récursion quand la donnée est emboîtée (arborescences, expressions, structures imbriquées) ou quand l'algorithme coupe le problème en morceaux nettement plus petits (dichotomie, tri fusion, diviser pour régner). La profondeur y est petite et la clarté est supérieure;
• choisissez l'itération pour les parcours linéaires — une liste, un fichier, une suite —, c'est-à-dire pour l'écrasante majorité de ce que vous écrirez;
• si vous écrivez une récursion, mémoïsez dès que deux branches peuvent demander le même calcul. C'est la différence entre 69 appels et 29 860 703;
• si votre récursion peut être profonde, itérez. Un RecursionError en production est un incident; une boucle n'en produit jamais.

Les deux fautes du débutant

Synthèse

• Une fonction récursive s'appelle elle-même sur un problème strictement plus petit. Elle n'est pas circulaire parce que la descente est finie: elle atteint nécessairement un cas de base traité sans appel. Écrire une récursion, c'est écrire ces deux cas et vérifier la décroissance — pas dérouler les appels dans sa tête.
• Chaque appel crée un cadre dans la pile d'appels, avec ses propres variables locales. Les cadres s'empilent pendant la descente et se dépilent pendant la remontée, dans l'ordre inverse: le premier appelé est le dernier à retourner. La pile est finie, et CPython la plafonne à 1000 cadres, d'où le RecursionError: maximum recursion depth exceeded.
• La factorielle illustre la traduction directe d'une relation de récurrence; sa profondeur vaut $n+1$ et la version itérative, mesurée ici deux à trois fois plus rapide, lui est préférable en pratique.
• La version naïve de Fibonacci est le contre-exemple à retenir: 2 692 537 appels pour $n=30$, 1,838 s pour $n=35$ et 21,2 s pour $n=40$, parce qu'elle recalcule les mêmes valeurs un nombre exponentiel de fois. La avec un dictionnaire ramène le nombre d'appels à — 69 appels pour — et le temps à quelques microsecondes.

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

def compter(chaine, caractere):
    """Nombre d'occurrences de caractere dans chaine."""
    if chaine == "":                  # cas de base: chaine vide
        return 0
    if chaine[0] == caractere:
        return

def somme_chiffres(n):
    """Somme des chiffres de l'entier n >= 0."""
    if n < 10:                       # cas de base: un seul chiffre
        return n
    return n % 10 + somme_chiffres(n // 10)

appels = 0


def montees

Références

• Downey, Think Python, 2ᵉ édition, O'Reilly — chapitre 5 («Conditionals and recursion») et chapitre 6 («Fruitful functions»), pour la pile d'appels et le saut de foi récursif. Disponible librement en ligne.
• Swinnen, Apprendre à programmer avec Python 3, Eyrolles — le chapitre consacré aux fonctions et à la récursivité, en français, avec les mêmes exemples de factorielle et de Hanoï.
• Matthes, Python Crash Course, 3ᵉ édition, No Starch Press — pour les fonctions, les dictionnaires et la construction d'un cache.
• Guttag, Introduction to Computation and Programming Using Python, MIT Press — chapitre «Recursion and global variables», qui traite Fibonacci, la mémoïsation et le coût exponentiel avec la rigueur d'un cours d'algorithmique.
• La documentation officielle Python, section «sys» du manuel de la bibliothèque standard, pour sys.getrecursionlimit et sys.setrecursionlimit, et section «functools» pour le décorateur cache.
• Le tutoriel officiel Python, section «Defining Functions», pour la portée des variables et le piège des arguments par défaut mutables.