La récursivité en Python : une fonction qui s'appelle elle-même

Définition

Certains problèmes se décrivent mieux en fonction d'eux-mêmes qu'en une suite d'étapes. Calculer la factorielle de 5, c'est calculer 5 fois la factorielle de 4. Parcourir un dossier, c'est traiter ses fichiers puis parcourir chacun de ses sous-dossiers de la même façon. Une boucle classique s'y prête mal, car elle suppose de connaître à l'avance le nombre de tours à faire.

La récursivité répond à ce besoin : une fonction s'appelle elle-même, traite sa part du travail, puis confie le reste à une nouvelle copie d'elle-même, jusqu'à un cas assez simple pour être réglé sans déléguer davantage. Sur la factorielle, cela donne ceci.

def factorielle(n):
    if n <= 1:
        return 1
    return n * factorielle(n - 1)

print(factorielle(5))    # 120

Rien dans la syntaxe ne signale une fonction récursive : le mot-clé def est le même que partout, c'est le corps qui la rend récursive, en mentionnant son propre nom. Python exécute l'appel demandé sans se soucier de savoir s'il pointe vers la fonction en cours ou vers une autre.

Les deux pieds sur lesquels elle tient

Une fonction qui s'appelle elle-même prend un risque qu'une boucle ne prend pas : si rien ne l'arrête, elle continue indéfiniment. Une fonction récursive correcte tient donc sur deux appuis.

Le mot « strictement » compte plus qu'il n'y paraît : un appel lancé sur un problème de même taille tourne sans jamais s'arrêter, comme un if dont la condition ne changerait jamais. Python finit alors par lever une RecursionError vers le millième appel, et le traceback répète la même ligne, signe que le cas de base manque.

Ce que fait la pile d'appels

La difficulté n'est pas d'écrire une fonction récursive, c'est de se représenter ce qui se produit à l'exécution. Chaque appel en cours occupe une place dans la pile, avec ses propres variables, libérée seulement quand il rend sa valeur. Voici ce que cela donne pour factorielle(3).

factorielle(3)
    3 * factorielle(2)
        2 * factorielle(1)
            1              # cas de base, la descente s'arrête
        2 * 1 = 2
    3 * 2 = 6

Le calcul se déroule en deux mouvements : une descente qui empile les appels en attente, puis une remontée qui les résout un par un. Le premier appel est donc le dernier à se terminer, et une fonction récursive consomme de la mémoire selon sa profondeur, là où une boucle en consomme une quantité fixe.

Récursivité ou boucle : le vrai critère

Le choix ne relève pas du goût personnel, il dépend de la forme de la donnée à parcourir : la structure se ramifie-t-elle ? Le tableau suivant fait le tour des cas courants.

Sur une liste plate, la récursivité n'apporte rien et coûte une pile pour rien : un simple parcours fait aussi bien. Sur une structure qui se ramifie, elle apporte beaucoup : le code épouse la forme de la donnée, là où un parcours itératif obligerait à tenir soi-même une pile des éléments restants.

Le piège du calcul refait mille fois

Une fonction récursive parfaitement juste peut malgré tout être catastrophiquement lente. Le cas d'école est la suite de Fibonacci écrite sans précaution : chaque appel en déclenche deux, et les mêmes valeurs sont recalculées un nombre de fois qui explose avec la profondeur.

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

fibo(35)    # plusieurs secondes d'attente

La correction ne touche pas à l'algorithme : elle mémorise les résultats déjà obtenus, pour ne plus les recalculer. Le décorateur lru_cache, fourni par le module functools de la bibliothèque standard, s'en charge en une seule ligne.

from functools import lru_cache

@lru_cache(maxsize=None)
def fibo(n):
    if n < 2:
        return n
    return fibo(n - 1) + fibo(n - 2)

fibo(35)    # instantané

Le gain se compte en ordres de grandeur pour une seule ligne ajoutée. Dès qu'une fonction récursive s'appelle plusieurs fois par niveau, comme ici avec fibo, elle repasse presque toujours sur les mêmes valeurs : vérifier si une mémorisation s'applique devient le premier réflexe.

Questions fréquentes

À travail égal, oui, légèrement : chaque appel coûte la création d'un contexte d'exécution, là où un tour de boucle ne coûte rien de tel. L'écart reste faible et ne justifie jamais de tordre un parcours d'arbre pour l'entrer dans une boucle. Ce qui coûte cher, c'est le calcul refait plusieurs fois sans mémorisation.

Oui, on parle alors de récursivité mutuelle : un cas de base quelque part dans le cycle, et chaque tour qui réduit le problème. Elle est plus difficile à repérer, puisqu'isolée, chaque fonction paraît irréprochable.

Affichez la profondeur avec les arguments, grâce à un paramètre de niveau incrémenté à chaque appel et à une indentation qui le suit. La trace montre la descente et la remontée sur une seule page, et le cas de base fautif y saute aux yeux bien plus vite qu'en avançant pas à pas dans un débogueur.