La récursivité

La factorielle se définit mathématiquement par $0!=1$ et $n!=n\times (n-1)!$ pour $n\ge 1$. Cette définition se traduit directement en code récursif :

def factorielle(n):
    if n == 0:          # cas de base
        return 1
    else:               # cas recursif
        return n * factorielle(n - 1)

print(factorielle(5))   # affiche 120

Le cas de base est $n=0$, le cas récursif appelle factorielle(n - 1), dont l'argument est strictement plus petit.

Lors d'un appel récursif, chaque appel non encore terminé reste dans la pile en attendant le résultat de l'appel qu'il a déclenché. La profondeur maximale atteinte par la pile correspond au nombre maximal d'appels imbriqués simultanément actifs.

L'évaluation de factorielle(3) provoque l'empilement suivant. On empile d'abord les appels, puis on les dépile en remontant les résultats :

factorielle(3)
= 3 * factorielle(2)
= 3 * (2 * factorielle(1))
= 3 * (2 * (1 * factorielle(0)))
= 3 * (2 * (1 * 1))      # factorielle(0) renvoie 1 (cas de base)
= 3 * (2 * 1)
= 3 * 2
= 6

À la profondeur maximale, quatre appels (factorielle(3), (2), (1) et (0)) coexistent dans la pile.

Si à chaque appel récursif on peut associer un variant entier positif qui décroît strictement, et si le ou les cas de base sont atteints lorsque le variant ne peut plus décroître, alors la fonction termine pour toute entrée valide.

Pour factorielle(n) avec $n\ge 0$, le variant est l'entier $n$ lui-même. À chaque appel, l'argument passe de $n$ à $n-1$ : il décroît strictement et reste positif jusqu'à atteindre $0$, qui est le cas de base. La fonction termine donc pour tout $n\ge 0$.

Attention : si on appelle factorielle(-1), le cas de base $n=0$ n'est jamais atteint et la fonction provoque un dépassement de pile. Il est donc essentiel de vérifier le domaine de validité des arguments.

La correction d'une fonction récursive se démontre par récurrence sur le variant :

• Initialisation : on vérifie que la fonction renvoie le bon résultat pour le ou les cas de base.
• Hérédité : on suppose que les appels récursifs (sur des instances plus petites) renvoient le résultat correct, et on en déduit que la combinaison effectuée dans le cas récursif donne le résultat attendu.

La somme $1+2+\cdots +n$ vérifie $S(0)=0$ et $S(n)=n+S(n-1)$.

def somme(n):
    if n == 0:
        return 0
    return n + somme(n - 1)

print(somme(100))   # affiche 5050

La suite de Fibonacci est définie par $F(0)=0$, $F(1)=1$ et $F(n)=F(n-1)+F(n-2)$ pour $n\ge 2$. Ici chaque appel en déclenche deux : on parle de récursivité multiple (ou arborescente).

def fibonacci(n):
    if n < 2:                     # cas de base : F(0)=0, F(1)=1
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(10))   # affiche 55

Cette version est très lisible mais inefficace : de nombreux sous-problèmes identiques sont recalculés (voir la section sur le coût).

Le problème des tours de Hanoï consiste à déplacer une tour de $n$ disques d'un piquet depart vers un piquet arrivee, à l'aide d'un piquet intermediaire, sans jamais poser un disque sur un disque plus petit. La solution récursive est remarquable :

• déplacer les $n-1$ disques supérieurs de depart vers intermediaire ;
• déplacer le plus grand disque de depart vers arrivee ;
• déplacer les $n-1$ disques de intermediaire vers arrivee.

def hanoi(n, depart, arrivee, intermediaire):
    if n == 0:
        return
    hanoi(n - 1, depart, intermediaire, arrivee)
    print("Deplacer disque", n, "de", depart, "vers", arrivee)
    hanoi(n - 1, intermediaire, arrivee, depart)

hanoi(3, "A", "C", "B")

Le nombre de déplacements nécessaires pour $n$ disques est $2^n-1$.

On cherche le nombre minimal de pièces nécessaires pour rendre une somme donnée à partir d'un système de valeurs. Une formulation récursive essaie chaque pièce et conserve le meilleur résultat :

def rendu(somme, pieces):
    if somme == 0:
        return 0
    meilleur = float("inf")
    for p in pieces:
        if p <= somme:
            essai = rendu(somme - p, pieces)
            if essai + 1 < meilleur:
                meilleur = essai + 1
    return meilleur

print(rendu(11, [1, 2, 5]))   # affiche 3  (5 + 5 + 1)

Cette version exhaustive donne toujours la solution optimale, mais son coût croît rapidement avec la somme à rendre.

Tout calcul exprimable de façon récursive peut l'être de façon itérative (à l'aide de boucles), et réciproquement. Le choix entre les deux relève de la lisibilité, de l'efficacité et de la nature du problème.

La même factorielle écrite avec une boucle, sans pile d'appels supplémentaire :

def factorielle_iter(n):
    resultat = 1
    for k in range(2, n + 1):
        resultat = resultat * k
    return resultat

print(factorielle_iter(5))   # affiche 120

La taille de la pile d'appels est bornée. En Python, une profondeur excessive provoque l'erreur RecursionError: maximum recursion depth exceeded (limite par défaut de l'ordre de 1000). Une récursion trop profonde ou infinie épuise la pile.

La version récursive naïve de Fibonacci a une complexité temporelle exponentielle, en $O({\phi }^n)$ où $\phi =\frac{1+\sqrt{5}}{2}$, car le même sous-problème est recalculé un grand nombre de fois. La version itérative (ou mémoïsée) ramène ce coût à $O(n)$.

En mémorisant les valeurs déjà calculées, on évite les recalculs et le coût devient linéaire :

def fibonacci_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n < 2:
        return n
    if n not in memo:
        memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

print(fibonacci_memo(50))   # rapide : 12586269025