Fonctions récursives

Les appels descendent par divisions de l'exposant : $\text{puissance}(2,10)\to (2,5)\to (2,2)\to (2,1)\to (2,0)$, qui renvoie $1$. La remontée calcule : $n=1$ (impair) : $2\cdot 1\cdot 1=2$ ; $n=2$ (pair) : $2\cdot 2=4$ ; $n=5$ (impair) : $2\cdot 4\cdot 4=32$ ; $n=10$ (pair) : $32\cdot 32=1024$. ✓ Profondeur maximale : $5$ contextes empilés ($\lfloor {\log }_{2}10\rfloor +2$). Multiplications : $2+1+2+1=6$ (deux par étage impair, une par étage pair, zéro au cas de base). (Tracer une exécution récursive, c'est dessiner la descente puis remonter en calculant — l'exercice qui rend la pile concrète.)

def renverse(s: str) -> str:
    if len(s) <= 1:                      # vide ou un caractère : son propre miroir
        return s
    return renverse(s[1:]) + s[0]        # le miroir de la queue, puis la tête

def est_palindrome(s: str) -> bool:
    if len(s) <= 1:
        return True
    return s[0] == s[-1] and est_palindrome(s[1:-1])

assert renverse("radar") == "radar" and renverse("info") == "ofni"
assert est_palindrome("kayak") and not est_palindrome("kayaks")

Variant commun : len(s), qui décroît de $1$ (resp. $2$) par appel. Correction de est_palindrome par récurrence forte : une chaîne de longueur $\le 1$ est un palindrome ; une chaîne plus longue en est un si et seulement si ses extrémités coïncident et que l'intérieur en est un — c'est la définition même. (Noter le court-circuit de and : si les extrémités diffèrent, l'appel récursif n'a pas lieu — la récursion s'arrête au premier désaccord, comme l'aurait fait une boucle.)

La pyramide de $n$ étages est la pyramide des $n-1$ premiers étages (avec le même décalage !) suivie de sa grande ligne. Il faut donc transmettre la largeur totale — un paramètre d'enrobage :

def etages(k: int, n: int) -> None:
    """Affiche les étages 1 à k d'une pyramide de n étages."""
    if k == 0:
        return
    etages(k - 1, n)
    print(" " * (n - k) + "*" * (2 * k - 1))

def pyramide(n: int) -> None:
    etages(n, n)

Le piège de l'exercice : écrire pyramide(n - 1) dans le cas récursif — la sous-pyramide serait alors centrée pour la largeur $n-1$, donc décalée d'un espace vers la gauche : tout l'édifice penche. La récursion porte sur $k$ (combien d'étages restent à dessiner), pas sur $n$ (la géométrie globale, qui ne change jamais). (Distinguer le paramètre qui décroît du paramètre de contexte : c'est le rôle de la fonction d'enrobage, déjà vue pour la dichotomie récursive.)

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

Pour $n=5$ : fib(5) appelle fib(4) et fib(3) ; fib(4) appelle fib(3) et fib(2)… Le compte donne $15$ appels, dont fib(2) calculé trois fois et fib(1) cinq fois. En notant $A(n)$ le nombre d'appels : $A(n)=1+A(n-1)+A(n-2)$, qui croît comme Fibonacci lui-même, donc exponentiellement (environ $1,618^n$) : fib(40) dépasse les $300$ millions d'appels. La cause : l'arbre des appels recalcule sans cesse les mêmes valeurs — exactement le piège des deux appels de l'exponentiation rapide, en pire.

Version itérative :

def fib_iter(n: int) -> int:
    a, b = 0, 1
    for _ in range(n):
        # Invariant : (a, b) == (F_k, F_{k+1}) au début du tour k
        a, b = b, a + b
    return a

$O(n)$ additions, profondeur de pile nulle. (La leçon n'est pas « la récursivité est lente » — la dichotomie récursive est excellente — mais : compter les appels ; quand l'arbre recalcule, soit on mémorise (la « mémoïsation », hors programme du semestre), soit on itère. Fibonacci est précisément l'exemple que le programme suggère de ne pas prendre pour modèle de la récursivité.)

import turtle

def sierpinski(longueur: float, n: int) -> None:
    """Trace le triangle de Sierpinski de niveau n (côté = longueur)."""
    if n == 0:
        for _ in range(3):               # cas de base : un triangle équilatéral
            turtle.forward(longueur)
            turtle.left(120)
        return
    sierpinski(longueur / 2, n - 1)      # coin en bas à gauche
    turtle.forward(longueur / 2)
    sierpinski(longueur / 2, n - 1)      # coin en bas à droite
    turtle.backward(longueur / 2)
    turtle.left(60)
    turtle.forward(longueur / 2)
    turtle.right(60)
    sierpinski(longueur / 2, n - 1)      # coin du haut
    turtle.left(60)
    turtle.backward(longueur / 2)
    turtle.right(60)

Chaque niveau triple les triangles : $3^n$ triangles élémentaires au niveau $n$, et $1+3+\cdots +3^n=\frac{3^{n+1}-1}{2}$ appels — exponentiel, comme Koch. Le point délicat du code n'est pas la récursion mais la remise en place : après chaque sous-triangle, la tortue doit revenir exactement à sa position et son cap d'origine, sinon les erreurs s'accumulent d'appel en appel. (Invariant géométrique : « chaque appel laisse la tortue là où il l'a trouvée » — un contrat de restitution d'état, qu'on retrouvera chaque fois qu'une récursion partage une ressource commune.)

On reprend la structure avec/sans de sous_listes, en filtrant à l'arrivée — ou mieux, en propageant la cible :

def sommes_possibles(t: list, cible: float) -> list:
    if t == []:
        return [[]] if cible == 0 else []
    sans = sommes_possibles(t[1:], cible)
    avec = [[t[0]] + s for s in sommes_possibles(t[1:], cible - t[0])]
    return sans + avec

assert sommes_possibles([2, 3, 5], 5) == [[5], [2, 3]]

def existe_somme(t: list, cible: float) -> bool:
    if t == []:
        return cible == 0
    return (existe_somme(t[1:], cible)
            or existe_somme(t[1:], cible - t[0]))

La version booléenne profite du court-circuit de or : dès qu'une branche répond True, l'autre n'est pas explorée — sur les instances favorables, une fraction seulement de l'arbre des $2^n$ feuilles est visitée. Le pire cas reste exponentiel : ce problème (« somme de sous-ensemble ») est l'un des grands problèmes difficiles de l'informatique, et l'énumération intelligente est, à ce jour, essentiellement ce qu'on sait faire. (Propager cible - t[0] plutôt que recalculer des sommes : l'argument transporte le travail déjà fait — le même réflexe d'accumulation qu'au chapitre 3.)

def nb_chiffres(n: int) -> int:          # récursif
    """Précondition : n >= 1."""
    if n < 10:
        return 1
    return 1 + nb_chiffres(n // 10)

def somme_chiffres(n: int) -> int:       # version boucle de la récursion évidente
    """Précondition : n >= 0."""
    s = 0
    while n > 0:
        s += n % 10
        n //= 10
    return s                             # s vaut 0 pour n = 0 : somme vide, correct

(Noter le cas $n=0$ : la boucle ne tourne pas et la fonction rend $0$, la somme vide — un cas que la version récursive doit aussi trancher explicitement.) Ces récursions sont terminales en esprit : un seul appel récursif, et le travail s'accumule linéairement — la boucle avec accumulateur en est la transcription mécanique : le paramètre devient une variable, l'appel devient un tour, le cas de base devient la condition d'arrêt. La conversion est nécessaire quand la profondeur $O(n)$ menace la pile (entiers à plus de mille chiffres ici — rares, mais possibles en Python) ; elle est toujours possible pour une récursion à un seul appel, et c'est un exercice de traduction sans risque dès lors qu'on transporte l'invariant. (Les récursions à plusieurs appels — Koch, sous-listes — se convertissent aussi, mais au prix d'une pile gérée à la main : on y reviendra avec les structures de données, au second semestre.)

Pour déplacer $n$ disques de A vers C : déplacer les $n-1$ du dessus vers B (récursivement), transférer le grand disque vers C, ramener les $n-1$ de B vers C :

def hanoi(n: int, depart: str, via: str, arrivee: str) -> None:
    if n == 0:
        return
    hanoi(n - 1, depart, arrivee, via)
    print(depart, "->", arrivee)
    hanoi(n - 1, via, depart, arrivee)

hanoi(3, "A", "B", "C")     # 7 déplacements

Compte : $D(n)=2D(n-1)+1$, $D(0)=0$ ; en posant $E(n)=D(n)+1$, on a $E(n)=2E(n-1)$ et $E(0)=1$, donc $E(n)=2^n$ et $D(n)=2^n-1$.

Optimalité : notons $M(n)$ le nombre minimal de déplacements. Pour bouger le plus grand disque, les $n-1$ autres doivent être tous sur la tige restante : cela coûte au moins $M(n-1)$ avant, puis $1$, puis au moins $M(n-1)$ pour les remettre dessus — d'où $M(n)\ge 2M(n-1)+1$, et par récurrence $M(n)\ge 2^n-1$. Notre algorithme atteint cette borne : il est optimal, et la difficulté est dans le problème, pas dans notre solution. (La légende veut que des moines déplacent $64$ disques d'or : $2^{64}-1\approx 1,8\cdot 10^{19}$ déplacements — à un par seconde, près de six cents milliards d'années. Le mur exponentiel, version monastique ; et un deuxième exemple, après la dichotomie, de borne inférieure prouvée par un argument de structure.)

def gray(n: int) -> list:
    """Les 2**n mots binaires, voisins à un bit près."""
    if n == 0:
        return [""]
    g = gray(n - 1)
    return ["0" + m for m in g] + ["1" + m for m in reversed(g)]

assert gray(2) == ["00", "01", "11", "10"]
for n in range(1, 10):                      # vérification de la propriété
    mots = gray(n)
    assert len(mots) == 2 ** n and len(set(mots)) == 2 ** n
    for a, b in zip(mots, mots[1:]):
        assert sum(1 for x, y in zip(a, b) if x != y) == 1

Preuve par récurrence. Pour $n=0$ : un seul mot, rien à vérifier. Supposons gray($n-1$) correcte (tous les mots, chacun une fois, voisins à un bit). Dans la première moitié, les mots préfixés par $0$ héritent de la propriété ; de même dans la seconde (renverser une liste préserve la voisinage des consécutifs). Au point de jonction, les deux mots sont $0m$ et $1m$ pour le même $m$ (dernier de $g$, premier de $g$ renversée) : ils diffèrent du seul bit de tête. ✓ Et tous les mots de longueur $n$ sont obtenus une fois chacun ($2^{n-1}+2^{n-1}=2^n$, sans collision entre les deux moitiés). (Le code de Gray est utilisé dans les codeurs angulaires matériels : entre deux positions voisines, un seul capteur change — toute lecture pendant la transition reste à un bit de la vérité. L'astuce du renversement, dite « réflexion », est le geste récursif à retenir : recoller deux copies dont l'une est retournée pour que la couture soit propre.)

Le tableau enseigne une hiérarchie des ressources : pour fib et sous_listes, le temps ou la mémoire du résultat explosent bien avant la pile — la profondeur n'est le facteur limitant que pour les récursions linéaires et rapides comme somme_jusqua. D'où la règle de conception : profondeur $O(\log n)$, toujours licite ; profondeur $O(n)$, licite si $n$ reste petit (chaînes, listes courtes) et à convertir en boucle sinon ; et avant toute conversion, vérifier que ce n'est pas le nombre total d'appels qui condamne l'approche. (Estimer les trois ressources — temps, pile, mémoire du résultat — avant d'exécuter : c'est l'analyse de complexité élargie, et elle évite la séance de débogage la plus frustrante qui soit, celle d'un programme correct qui ne peut simplement pas finir.)