Récursivité.

• Dérouler une fonction récursive à la main et prédire son résultat.
• Écrire factorielle, puissance, Fibonacci, Hanoï, un parcours de labyrinthe.
• Expliquer RecursionError et la pile d’appels.
• Reconnaître un problème « naturellement récursif ».

factorielle(3) → 3 × factorielle(2) → 3 × (2 × factorielle(1)) → 3 × (2 × (1 × factorielle(0))) → 3 × (2 × (1 × 1)) → 6. Les multiplications s’effectuent en remontant, une fois le cas de base atteint. Chaque appel en attente est stocké : c’est la pile.

Chaque appel de fonction crée un « cadre » avec ses variables locales, empilé au-dessus de l’appelant. Quand la fonction renvoie, le cadre est retiré. Python limite la pile à ~1000 cadres pour éviter qu’un bug ne consomme toute la mémoire : d’où RecursionError. Une boucle n’a pas cette limite. Sur un microcontrôleur avec 2 Ko de RAM, la pile est minuscule : la récursivité profonde y est proscrite.

x¹⁰⁰ = (x⁵⁰)². Si on écrivait puissance_rapide(x, n//2) * puissance_rapide(x, n//2), on ferait le même calcul deux fois et on perdrait tout le gain. On le fait une fois et on le stocke. Complexité : O(log n) au lieu de O(n). Cet algorithme (exponentiation rapide) est au cœur du chiffrement RSA, où l’on calcule des puissances avec des exposants de 600 chiffres : impossible sans lui. Séance 13.

fib(30) appelle fib(29) et fib(28) ; fib(29) appelle fib(28) et fib(27)… fib(28) est calculé deux fois, fib(27) trois fois, fib(20) plus de 10 000 fois. Nombre total d’appels ≈ 1,6ⁿ : exponentiel. La mémoïsation (un dictionnaire des résultats connus) ramène à n appels utiles. Python fournit le décorateur @functools.lru_cache qui fait exactement cela. Leçon : la récursivité est élégante, mais il faut compter les appels comme on compte les tours de boucle.

C(n) = 2·C(n−1) + 1, C(0) = 0, donc C(n) = 2ⁿ − 1. Prouvez-le par récurrence : c’est exactement la structure de la fonction. Pour 64 disques (la légende) : 1,8 × 10¹⁹ coups, soit 585 milliards d’années à un coup par seconde. Le raisonnement « je suppose que je sais faire pour n−1, j’en déduis n » est le raisonnement par récurrence des mathématiques : la récursivité en est la traduction directe en code. Une version itérative existe mais elle est bien moins lisible.

somme et inverser se font mieux en boucle (et liste[1:] recopie la liste : O(n²) au total). Mais aplatir traite une structure dont la profondeur est inconnue : une boucle ne suffit pas, il faudrait gérer une pile à la main. Règle : la récursivité s’impose quand les données sont elles-mêmes récursives (listes imbriquées, arbres, dossiers contenant des dossiers, expressions mathématiques).

À chaque case, on essaie les quatre directions. Si l’une mène à la sortie, on remonte True. Si aucune ne marche, on retire la case du chemin (pop) et on renvoie False : l’appelant essaiera une autre direction. Ce schéma « essayer, et défaire si ça échoue » s’appelle le retour sur trace (backtracking). Il résout le sudoku, les huit reines, la planification d’un robot… Le marquage « visité » est indispensable : sans lui, on tournerait en rond. Le chemin trouvé n’est pas forcément le plus court : pour cela, séance 18 (BFS).

À chaque niveau, le nombre de segments est multiplié par 4 et la longueur par 4/3. À la limite, la courbe a une longueur infinie mais tient dans un rectangle. C’est une fractale, de dimension log 4 / log 3 ≈ 1,26 — ni une ligne, ni une surface. Sur votre PC, dessinez les segments avec le module turtle (livré avec Python) ou avec matplotlib (séance 19) : le résultat est spectaculaire. Les fractales modélisent les côtes, les poumons, les antennes de téléphone.

def somme_chiffres(n):
    if n < 10:
        return n
    return n % 10 + somme_chiffres(n // 10)

def compte(x, liste):
    if not liste:
        return 0
    return (1 if liste[0] == x else 0) + compte(x, liste[1:])

def pgcd(a, b):
    if b == 0:
        return a
    return pgcd(b, a % b)

def binaire(n):
    if n < 2:
        return str(n)
    return binaire(n // 2) + str(n % 2)

Pour binaire, le dernier bit est n % 2 et les autres sont l’écriture de n // 2 : la récursivité place naturellement les bits dans le bon ordre. Séance 13 approfondit.

def sous_ensembles(liste):
    if not liste:
        return [[]]
    reste = sous_ensembles(liste[1:])
    return reste + [[liste[0]] + s for s in reste]

def permutations(liste):
    if len(liste) <= 1:
        return [liste]
    resultat = []
    for i, x in enumerate(liste):
        for p in permutations(liste[:i] + liste[i + 1:]):
            resultat.append([x] + p)
    return resultat

import math
points = [(0, 0), (5, 2), (1, 7), (8, 8), (3, 4)]
def longueur(ordre):
    return sum(math.dist(ordre[i], ordre[i + 1]) for i in range(len(ordre) - 1))
meilleur = min(permutations(points), key=longueur)
print(meilleur, round(longueur(meilleur), 2))

C’est la force brute du voyageur de commerce (séance 10). 5 points : 120 essais, instantané. 10 points : 3,6 millions, quelques secondes. 15 points : 1,3 × 10¹², impossible. La récursivité rend l’énumération facile à écrire ; elle ne la rend pas rapide.

def reines(n, afficher_une=False):
    colonnes = []                      # colonnes[i] = colonne de la reine de la ligne i
    compte = 0

    def compatible(col):
        ligne = len(colonnes)
        for l, c in enumerate(colonnes):
            if c == col or abs(c - col) == abs(l - ligne):     # colonne ou diagonale
                return False
        return True

    def placer():
        nonlocal compte
        if len(colonnes) == n:
            compte += 1
            if afficher_une and compte == 1:
                for c in colonnes:
                    print("." * c + "Q" + "." * (n - c - 1))
            return
        for col in range(n):
            if compatible(col):
                colonnes.append(col)
                placer()
                colonnes.pop()          # défaire

    placer()
    return compte

reines(8, afficher_une=True)
for n in (4, 5, 6, 8, 10):
    print(n, reines(n))

Les diagonales : deux cases (l₁, c₁) et (l₂, c₂) sont sur une diagonale si |l₁ − l₂| = |c₁ − c₂|. Le pop() après l’appel récursif est le geste du backtracking : on essaie, on explore, on défait. nonlocal permet à la fonction interne de modifier compte. Pour n = 12, on trouve 14 200 solutions en quelques secondes ; n = 14 demande des minutes. Ce problème est un banc d’essai classique ; Dijkstra l’a utilisé en 1972 pour enseigner la programmation structurée. Ouverture : et si on voulait seulement une solution pour n = 1000 ? Il existe une formule directe — la force brute n’est pas toujours nécessaire.