La Récursivité Expliquée: Quand l'Utiliser et Quand l'Éviter

Une fonction qui s’appelle elle-même a une profondeur maximale, et elle est plus petite que ce que la plupart des gens imaginent : 1 000 appels dans CPython par défaut, à peu près 10 000 à 15 000 dans Node et dans les moteurs des navigateurs, selon ce que chaque frame contient. Dépasser cette limite ne ralentit pas le programme. Il plante. Python lève RecursionError: maximum recursion depth exceeded ; JavaScript lève RangeError: Maximum call stack size exceeded.

Les deux erreurs ont la même cause, et une fois qu’on l’a vue, on sait quand la récursivité est le bon outil et quand elle devient un risque.

Ce qu’une fonction récursive fait réellement à la pile d’appels

Chaque appel de fonction place un frame sur la pile : les arguments, les variables locales, l’adresse de retour. Un appel normal retourne et son frame est retiré. Un appel récursif ne peut pas encore retourner, car il attend l’appel qu’il vient de faire, donc chaque frame reste sur la pile jusqu’à ce que celui du dessous se termine.

1
2
3
4

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

factorial(4) construit quatre frames sur la pile avant qu’aucun d’eux ne produise une valeur :

1
2
3
4

factorial(4) -> 4 * factorial(3)
                     factorial(3) -> 3 * factorial(2)
                                          factorial(2) -> 2 * factorial(1)
                                                               factorial(1) -> 1   # cas de base, la pile arrête de grandir

Ce n’est que lorsque factorial(1) retourne 1 que la pile se déroule : 2 * 1, puis 3 * 2, puis 4 * 6, pour donner 24.

Ce mécanisme repose sur deux éléments. Le cas de base (n <= 1) arrête la récursion. Le cas récursif rappelle la fonction avec une entrée qui se rapproche du cas de base. Enlevez l’un des deux et la fonction ne s’arrête plus jamais de s’appeler elle-même : en Python, RecursionError arrive en moins de mille appels ; dans un langage sans limite, le processus meurt par dépassement de pile.

Quand la récursivité est le bon outil : des données imbriquées

La récursivité se justifie quand les données sont imbriquées à une profondeur inconnue à l’avance : un arbre, un système de fichiers, un JSON imbriqué sans limite fixe. Une boucle sur ce type de données a besoin d’une pile gérée à la main. La récursivité en fournit une gratuitement, car la pile d’appels est la pile dont on avait besoin.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def flatten(nested):
    result = []
    for item in nested:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result

flatten([1, [2, 3, [4, [5, 6]], 7], 8])
# [1, 2, 3, 4, 5, 6, 7, 8]

Chaque appel à flatten gère un niveau. Quand il rencontre une liste imbriquée, il la transmet à un nouvel appel, et la pile se souvient où reprendre dans la liste externe une fois la liste interne terminée. La version itérative devrait suivre cette position elle-même.

Parcourir une arborescence de répertoires a la même forme :

1
2
3
4
5
6

from pathlib import Path

def total_size(path: Path) -> int:
    if path.is_file():
        return path.stat().st_size
    return sum(total_size(child) for child in path.iterdir())

total_size ne se soucie pas qu’un répertoire ait un seul niveau ou dix. Chaque appel gère son propre path.

Quand la récursivité est le mauvais outil : une entrée plate et longue

Additionner une liste plate est le cas opposé. Il n’y a aucune imbrication, donc la récursivité n’apporte rien, sinon un risque de pile.

1
2
3
4

def sum_recursive(nums):
    if not nums:
        return 0
    return nums[0] + sum_recursive(nums[1:])

Elle fonctionne sur une petite entrée et échoue sur une entrée réelle :

1
2
3
4

>>> sum_recursive(list(range(2000)))
Traceback (most recent call last):
  ...
RecursionError: maximum recursion depth exceeded

Deux mille éléments, un frame par élément, soit le double de la limite par défaut. La version avec boucle utilise un seul frame, quelle que soit la longueur de la liste :

1
2
3
4
5

def sum_iterative(nums):
    total = 0
    for n in nums:
        total += n
    return total

sum_iterative(list(range(1_000_000))) retourne instantanément. En termes de notation Big O, les deux versions sont en O(n) en temps, mais la version récursive coûte aussi O(n) en espace de pile, et cet espace est limité à environ mille frames.

La tail-call optimization règle-t-elle la récursivité profonde en Python ou en JavaScript ?

Non. Dans sum_recursive, la dernière chose qui se produit est l’addition, pas l’appel récursif, donc chaque frame doit rester vivant pour recevoir un résultat et l’additionner. Vous pouvez la réécrire pour que l’appel récursif soit la toute dernière opération, en transportant le total courant comme argument :

1
2
3
4

def sum_tail(nums, acc=0):
    if not nums:
        return acc
    return sum_tail(nums[1:], acc + nums[0])

Dans un langage avec tail-call optimization, le compilateur voit que rien dans le frame de l’appelant n’est nécessaire après l’appel, et réutilise ce frame au lieu d’en empiler un nouveau. La récursivité devient une boucle en coulisses.

CPython ne le fait pas, par choix de conception : ses développeurs principaux l’ont rejetée parce qu’elle rendrait les tracebacks plus difficiles à lire. sum_tail atteint quand même la limite sur une liste de 2 000 éléments. La spécification ES2015 de JavaScript inclut les proper tail calls, mais V8 (Chrome, Node.js) et SpiderMonkey (Firefox) ne les ont jamais implémentées ; seul JavaScriptCore, le moteur de Safari, le fait.

La règle est donc la même dans les deux langages. Si la taille de l’entrée décide de la profondeur atteinte par la récursivité, ne comptez pas sur le moteur pour vous sauver. Convertissez-la en boucle, ou plafonnez la profondeur.

Comment la mémoïsation corrige une récursivité lente

Certaines fonctions récursives n’approchent jamais la limite de profondeur. Leur problème, c’est qu’elles recalculent la même chose encore et encore. Le Fibonacci récursif naïf est le cas d’école :

1
2
3
4

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

fib(5) appelle fib(4) et fib(3), et fib(4) rappelle fib(3). Cette duplication s’accumule à chaque niveau, donc le nombre d’appels croît de façon exponentielle avec n (par un facteur d’environ 1,6 à chaque étape, souvent écrit comme la borne supérieure O(2^n)). Sous CPython, fib(30) prend déjà environ un dixième de seconde et fib(40) plus de dix secondes.

La correction laisse la récursivité intacte et met les résultats en cache, pour que chaque entrée distincte soit calculée une seule fois :

1
2
3
4
5
6
7

from functools import lru_cache

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

lru_cache est un décorateur. Il enveloppe fib_memo, et quand un argument se répète, il renvoie le résultat stocké au lieu de réexécuter le corps de la fonction. fib_memo(40) retourne instantanément.

La profondeur ne change pas : fib_memo(40) a toujours besoin d’environ 40 frames de pile. Ce qui change, c’est le nombre d’appels, qui passe d’exponentiel à linéaire. Vous payez O(n) de mémoire pour le cache et obtenez O(n) en temps au lieu d’exponentiel.

Récursivité ou itération : laquelle choisir

Un cas mérite plus qu’une ligne de tableau. Si la profondeur de la récursivité est contrôlée par une entrée à laquelle vous ne faites pas confiance, c’est un vecteur de déni de service. Un analyseur récursif qui descend d’un niveau par crochet imbriqué dans un texte fourni par l’utilisateur peut être planté par quiconque envoie quelques milliers de caractères [. Plafonnez la profondeur explicitement, ou ne récursez pas.

Comment convertir une fonction récursive en boucle

Le remplacement direct de la récursivité sur un arbre est une pile explicite : une list sur laquelle vous faites push et pop à la main, pilotée par une boucle while. Voici flatten réécrite ainsi :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def flatten_iterative(nested):
    result = []
    stack = [iter(nested)]
    while stack:
        for item in stack[-1]:
            if isinstance(item, list):
                stack.append(iter(item))
                break
            result.append(item)
        else:
            stack.pop()
    return result

Elle produit le même résultat avec un seul frame de pile, quelle que soit la profondeur de l’entrée. Le coût, c’est la gestion que vous voyez à l’œil : la pile d’itérateurs est exactement ce que la pile d’appels suivait pour vous.

La prochaine fois que vous écrivez une fonction récursive, demandez-vous jusqu’où elle peut descendre. Si la réponse est petite et connue (un fichier de configuration, un arbre de composants d’interface, un arbre de syntaxe pour votre propre grammaire), gardez la récursivité. Si la réponse est « ce que dit l’entrée », écrivez la boucle.

Articles associés

• La Notation Big O Expliquée avec des Exemples de Code
• Git Bisect : trouver le commit qui a introduit un bug