Programmation · concepts · récursion

Qu'est-ce que la récursion ?

Certains problèmes sont naturellement auto-similaires : un dossier contient des dossiers, une phrase est faite de propositions faites de mots, une grande somme n'est qu'un nombre plus une somme plus petite. La récursion est la technique de programmation qui épouse directement cette forme — une fonction qui résout un problème en s'appelant elle-même sur une version plus petite du même problème. Ce guide explique ce qu'est réellement la récursion, les deux ingrédients indispensables, des exemples de code réels, la comparaison avec les boucles, ce qu'est la récursion terminale, les pièges classiques, et pourquoi elle est au cœur de la programmation fonctionnelle.

La définition courte

La récursion, c'est quand une fonction s'appelle elle-même pour résoudre un problème en le réduisant à une ou plusieurs instances plus petites du même problème. Chaque appel traite un morceau un peu plus petit, et les appels se poursuivent jusqu'à ce que le problème soit assez simple pour être résolu directement. À ce moment-là, les réponses se recombinent en remontant pour résoudre le problème d'origine.

Les deux ingrédients

Toute fonction récursive correcte comporte exactement deux parties. Il suffit d'en oublier une pour que tout casse.

1. Le cas de base. C'est la plus petite version du problème que l'on peut résoudre sans récursion — c'est lui qui arrête la récursion. Pour la factorielle, le cas de base est 0! = 1. Pour la somme d'une liste, c'est la liste vide, dont la somme vaut 0.

2. Le cas récursif. Il traite le problème général en faisant un peu de travail, puis en rappelant la fonction sur une entrée plus petite, qui se rapproche du cas de base. Le mot qui compte est plus petite : si l'appel récursif ne porte pas sur un problème réellement plus petit, on n'atteint jamais le cas de base.

Sans cas de base atteignable, une fonction récursive s'appelle indéfiniment. En pratique, elle ne boucle pas en silence : elle épuise la pile d'appels du programme et plante avec un débordement de pile (stack overflow).

Premier exemple : la factorielle

La factorielle d'un nombre n (notée n!) vaut n × (n-1) × … × 1. Sa structure récursive est évidente : n! = n × (n-1)!, avec 0! = 1. En Python :

def factorial(n):
    if n == 0:          # cas de base
        return 1
    return n * factorial(n - 1)   # cas recursif, sur un n plus petit

factorial(5)   # 120

Déroulez-la : factorial(5) attend factorial(4), qui attend factorial(3), jusqu'à factorial(0), qui renvoie 1 directement. Les réponses se multiplient ensuite en remontant : 1 → 1 → 2 → 6 → 24 → 120. La même idée en Haskell, où la récursion est l'outil quotidien pour ce type de boucle :

factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n - 1)

D'autres exemples

Sommer une liste. La somme d'une liste est son premier élément plus la somme du reste ; la somme d'une liste vide vaut zéro.

# Python
def total(xs):
    if not xs:          # cas de base : liste vide
        return 0
    return xs[0] + total(xs[1:])

total([3, 1, 4, 1])     # 9

-- Haskell
total :: [Int] -> Int
total []     = 0
total (x:xs) = x + total xs

Parcourir un arbre. La récursion brille sur les données imbriquées et auto-similaires — précisément là où les boucles deviennent pénibles. Pour compter les nœuds d'un arbre binaire, on compte ce nœud plus les nœuds de chaque sous-arbre :

# Python : un noeud est un dict avec des enfants left/right optionnels
def count_nodes(node):
    if node is None:        # cas de base : sous-arbre vide
        return 0
    return 1 + count_nodes(node["left"]) + count_nodes(node["right"])

Remarquez la même forme à chaque fois : un cas de base pour la plus petite entrée, et un cas récursif qui combine les résultats d'entrées plus petites.

Récursion contre itération

Tout ce qui s'écrit avec la récursion s'écrit aussi avec une boucle (itération), et réciproquement — les deux ont la même puissance. Le choix porte sur la clarté et le coût.

La récursion se lit souvent plus naturellement pour les problèmes auto-similaires (arbres, structures imbriquées, algorithmes « diviser pour régner » comme le tri rapide ou le tri fusion). Son inconvénient : chaque appel consomme une trame de pile, donc une récursion profonde peut coûter beaucoup de mémoire, voire faire déborder la pile.

L'itération (une boucle for ou while) utilise un espace de pile constant et se révèle généralement plus rapide dans les langages qui n'optimisent pas les appels récursifs. Elle peut être plus claire pour un travail simple et linéaire du type « faire ceci N fois ». La factorielle ci-dessus en est un bon exemple : une boucle la calcule sans faire croître la pile du tout.

Règle empirique : privilégiez la récursion quand les données ou l'algorithme sont naturellement récursifs et que la profondeur est bornée ; privilégiez une boucle quand le travail est plat et que la performance brute ou une itération très profonde compte.

La récursion terminale, et pourquoi elle compte

Un appel récursif est en position terminale quand il est la toute dernière chose que fait la fonction : son résultat est renvoyé directement, sans traitement en attente. La première factorial ci-dessus n'est pas terminale : après le retour de factorial(n - 1), il reste une multiplication à faire, donc chaque appel doit rester sur la pile. On peut la réécrire en transportant le résultat courant dans un accumulateur, de sorte que l'appel récursif soit la dernière étape :

def factorial(n, acc=1):
    if n == 0:
        return acc
    return factorial(n - 1, acc * n)   # appel terminal : plus rien apres

Quand l'appel récursif est en position terminale, un compilateur peut effectuer l'optimisation d'appel terminal (TCO) : réutiliser la trame de pile courante au lieu d'en empiler une nouvelle, ce qui rend la récursion aussi économique qu'une boucle et supprime le risque de débordement. Que cela se produise dépend du langage : Scheme et beaucoup de langages fonctionnels garantissent la TCO, et le modèle paresseux de Haskell, optimisé par GHC, traite souvent efficacement la récursion à accumulateur. Point crucial : CPython ne fait pas de TCO — Python conserve chaque trame et plafonne même la profondeur de récursion (environ 1000 par défaut), si bien que la version terminale ci-dessus n'apporte aucun bénéfice en Python, où une simple boucle est le choix idiomatique. Vérifiez toujours votre langage avant de compter sur une récursion terminale profonde.

Les pièges classiques

Cas de base absent ou inatteignable. Le bug numéro un. Si aucun appel n'atteint jamais le cas de base (ou si l'entrée ne rétrécit pas réellement), vous obtenez une récursion infinie et un débordement de pile.

Trop de profondeur. Même correcte, une récursion peut déborder sur de très grandes entrées dans les langages sans TCO. Si vous risquez de descendre à des dizaines de milliers de niveaux, préférez l'itération ou une pile explicite.

Travail redondant. La suite de Fibonacci récursive naïve recalcule sans cesse les mêmes valeurs :

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)   # recalcule des sous-problemes qui se recouvrent

Elle se ramifie en deux appels environ à chaque niveau, si bien que son temps d'exécution croît exponentiellement — fib(40) engendre déjà des centaines de millions d'appels. Le remède est la mémoïsation : mettre en cache chaque résultat au premier calcul, pour que les sous-problèmes répétés soient résolus instantanément.

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)   # chaque n n est calcule qu une fois

Avec le cache, la même récursion s'exécute en temps linéaire. La leçon : la récursion décrit clairement ce qu'il faut calculer, mais il reste à surveiller la quantité de travail que les appels dupliquent réellement.

Récursion et programmation fonctionnelle

En programmation fonctionnelle, la récursion assure une bonne part du travail que les boucles font en style impératif. Comme le style fonctionnel pur évite les compteurs de boucle mutables et les modifications sur place, la répétition s'exprime par une fonction qui s'appelle elle-même sur des données plus petites — exactement les exemples de listes et d'arbres ci-dessus. Des langages comme Haskell s'appuient sur la récursion (et sur des fonctions d'ordre supérieur comme map et fold, elles-mêmes récursives en dessous), et l'évaluation paresseuse de Haskell permet même à la récursion de définir des structures infinies, calculées seulement aussi loin que vous les lisez.

Questions fréquentes

À lire aussi : Qu'est-ce qu'un algorithme · Qu'est-ce qu'une variable · index des guides