Récursivité

Introduction

Une fonction récursive est une fonction qui s'appelle elle-même. Cette notion d'auto-référence, étrangère au calcul itératif, est l'un des outils les plus puissants du programmeur — et l'un des plus subtils à analyser. Elle est le cœur de l'item [TD05].

Beaucoup de problèmes ont une structure récursive naturelle : la taille d'un arbre, le parcours d'un graphe, le calcul d'une factorielle, la décomposition d'un problème en sous-problèmes plus petits. Écrire la solution récursive est souvent plus court et plus lisible que sa version itérative — mais l'analyse de coût demande un outillage spécifique.

L'idée est partout dans la culture : les matriochkas russes (chaque poupée contient une poupée plus petite, jusqu'à une dernière insécable), l'effet Droste (la vieille boîte de cacao Van Houten où une infirmière tient une boîte… qui contient l'infirmière qui tient la boîte), ou encore la fractale de Sierpinski (chaque triangle est composé de trois triangles identiques à plus petite échelle).

Anatomie d'une fonction récursive

Toute fonction récursive bien formée a deux ingrédients :

1. Un ou plusieurs cas de base — une situation où la fonction retourne directement, sans s'appeler. C'est la condition de terminaison.
2. Un cas récursif — la fonction se rappelle sur une entrée strictement plus petite (au sens d'un ordre bien fondé), et combine le résultat.

Exemple canonique : la factorielle.

def factorielle(n: int) -> int:
    """Calcule n! par récurrence.

    >>> factorielle(0)
    1
    >>> factorielle(5)
    120
    """
    assert n >= 0, "n doit être positif ou nul"
    if n == 0:              # cas de base
        return 1
    return n * factorielle(n - 1)   # cas récursif

La pile d'appels — ce qui se passe vraiment

Chaque appel de fonction empile un cadre d'activation sur la pile d'appels (stack en anglais). On l'imagine comme une pile d'assiettes dans un placard : on ne pose et on ne retire qu'au sommet, et l'assiette tout en bas — le premier appel — n'est libérée qu'en dernier. Pour factorielle(3), la pile se déploie ainsi :

factorielle(3)        ← retour : 3 * factorielle(2)
  factorielle(2)      ← retour : 2 * factorielle(1)
    factorielle(1)    ← retour : 1 * factorielle(0)
      factorielle(0)  ← retour : 1

Puis la pile se dépile dans l'ordre inverse : $1 \to 1 \times 1 = 1 \to 2 \times 1 = 2 \to 3 \times 2 = 6$.

Complexité — la factorielle est linéaire

Notons $T(n)$ le nombre d'opérations pour calculer factorielle(n). La définition récursive donne directement :

$T(n) = T(n-1) + O(1) \quad \text{avec} \quad T(0) = O(1)$

En déroulant : $T(n) = T(n-1) + c = T(n-2) + 2c = \dots = T(0) + nc$, soit $T(n) = O(n)$. La factorielle récursive est linéaire — exactement comme sa version itérative.

Fibonacci naïf — l'explosion exponentielle

Considérons Fibonacci : $F_0 = 0$, $F_1 = 1$, $F_n = F_{n-1} + F_{n-2}$.

def fib_naif(n: int) -> int:
    """Fibonacci, version récursive directe."""
    assert n >= 0
    if n < 2:
        return n
    return fib_naif(n - 1) + fib_naif(n - 2)

Chaque appel en déclenche deux. La relation de récurrence devient :

$T(n) = T(n-1) + T(n-2) + O(1)$

On montre que $T(n) = O(\varphi^n)$ avec $\varphi = \frac{1 + \sqrt{5}}{2} \approx 1{,}618$ — autrement dit, exponentielle. En pratique, fib_naif(40) prend déjà plusieurs secondes ; fib_naif(60) est inatteignable.

La raison : fib_naif(40) recalcule fib_naif(38) deux fois, fib_naif(37) trois fois, fib_naif(36) cinq fois… exponentiellement.

Mémoïsation — de $O(2^n)$ à $O(n)$

La mémoïsation mémorise chaque résultat déjà calculé. Une valeur n'est calculée qu'une fois ; les appels suivants sont $O(1)$.

def fib_memo(n: int, cache: dict = None) -> int:
    """Fibonacci mémoïsé via un dictionnaire."""
    if cache is None:
        cache = {}
    if n in cache:
        return cache[n]
    if n < 2:
        return n
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]

Plus idiomatique en Python : utiliser le décorateur de la bibliothèque standard.

from functools import lru_cache

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

Nouveau coût : chaque valeur de 0 à n est calculée une fois.

$T(n) = O(n)$

Concrètement, fib(100) est instantané — alors que fib_naif(100) ne terminerait jamais.

Pour aller plus loin

La récursivité éclaire les structures arborescentes (chapitre TA) — la hauteur d'un arbre se calcule récursivement par 1 + max(hauteur(gauche), hauteur(droite)). Certains langages (Haskell, OCaml) optimisent la récursion terminale en boucle — Python ne le fait pas.