09 — Récursion & Backtracking : Cours complet

Niveau : Université — Durée : 4h de cours + 4h de TP Paradigme central pour l'algorithmique combinatoire, les parseurs, l'IA (mini-max), les moteurs de recherche et les solveurs.

---

Partie I — La récursion

1.1 Définition

Un algorithme récursif est un algorithme qui s'appelle lui-même, directement ou indirectement, sur une instance plus petite du même problème.

def factorielle(n: int) -> int:
    if n <= 1:           # cas de base
        return 1
    return n * factorielle(n - 1)   # relation de récurrence

Toute fonction récursive correcte a deux composantes obligatoires :

1. Cas de base (base case) : l'instance triviale résolue directement, sans appel récursif. Il garantit la terminaison.
2. Cas général (recurrence / inductive case) : on exprime la solution du problème en fonction de la solution d'un problème plus petit.

Règle d'or : tout appel récursif doit se rapprocher du cas de base (diminution stricte de la taille de l'instance). Sinon → récursion infinie → stack overflow.

1.2 Relation de récurrence et suite mathématique

Une relation de récurrence est l'équation mathématique qui décrit la complexité ou la valeur calculée.

Pour factorielle :

f(0) = 1
f(n) = n · f(n − 1)        pour n ≥ 1

Pour Fibonacci :

fib(0) = 0,  fib(1) = 1
fib(n) = fib(n − 1) + fib(n − 2)     pour n ≥ 2

La résolution de ces relations (substitution, arbre de récurrence, Master Theorem — chapitre 12) permet de calculer la complexité asymptotique.

1.3 La pile d'appels (call stack)

Chaque appel récursif pousse une stack frame sur la pile d'exécution :

Exemple d'exécution de factorial(3) :

main
│
├─ factorial(3)
│   ├─ factorial(2)
│   │   ├─ factorial(1)  → retourne 1
│   │   └─ retourne 2 * 1 = 2
│   └─ retourne 3 * 2 = 6
└─ affiche 6

Profondeur maximale : en C/C++ par défaut ~8 Mo (≈10⁵–10⁶ frames), en Python ~1000 frames (limite du interpreter). Une profondeur de n consomme O(n) en mémoire d'appels.

⚠️ Stack overflow : toute récursion de profondeur linéaire n avec n grand est risquée. On peut relever la limite en Python (sys.setrecursionlimit) mais mieux : passer à l'itératif ou à la tail recursion (si le langage l'optimise).

1.4 Formes de récursion

---

Partie II — Exemples fondamentaux

2.1 Somme d'un tableau

def somme(t: list, i: int = 0) -> int:
    if i == len(t):            # cas de base
        return 0
    return t[i] + somme(t, i + 1)   # découpage

La taille de l'instance diminue à chaque appel (i augmente) → terminaison garantie.

2.2 Fibonacci (version naïve)

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

Problème majeur : on recalcule sans cesse les mêmes valeurs. L'arbre de récursion a O(2ⁿ) nœuds.

2.3 Palindrome

def est_palindrome(s: str, gauche: int = 0, droite: int = None) -> bool:
    if droite is None:
        droite = len(s) - 1
    if gauche >= droite:             # cas de base
        return True
    if s[gauche] != s[droite]:       # échec rapide
        return False
    return est_palindrome(s, gauche + 1, droite - 1)

2.4 Exponentiation rapide (aperçu, détaillé chapitre 12)

def puissance(a: float, n: int) -> float:
    if n == 0:
        return 1
    if n % 2 == 0:
        return puissance(a, n // 2) ** 2
    return a * puissance(a, n // 2) ** 2

Complexité : O(log n) appels.

---

Partie III — Tail recursion (récursion terminale)

3.1 Définition

Une fonction est tail-récursive si l'appel récursif est la dernière opération exécutée — sa valeur est retournée telle quelle, sans traitement ultérieur.

# Pas tail : la multiplication se fait APRÈS le retour
def fact_1(n):
    if n == 0: return 1
    return n * fact_1(n - 1)

# Tail : le résultat est accumulé dans un paramètre
def fact_tail(n, acc=1):
    if n == 0: return acc
    return fact_tail(n - 1, n * acc)

3.2 Pourquoi c'est important

Avec une tail call optimization (TCO), le compilateur réutilise la frame courante au lieu d'en empiler une nouvelle → récursion en espace O(1), équivalente à une boucle.

3.3 Transformer une récursion en tail recursion

Technique : ajouter un paramètre accumulateur qui transporte le résultat partiel.

factorielle :   acc ← 1, à chaque étape acc ← n·acc
somme :         acc ← 0, à chaque étape acc ← acc + t[i]

3.4 Itératif = tail recursion (dans les langages sans TCO)

def fact_iter(n):
    acc = 1
    while n > 0:
        acc *= n
        n -= 1
    return acc

---

Partie IV — Arbre de récursion et complexité

4.1 Visualiser

Pour fib(5) :

Diagramme en cours de génération...

4.2 Compter les nœuds

• Récursion linéaire (somme, fact) : arbre en chaîne, O(n) nœuds.
• Récursion arborescente binaire (fib) : arbre binaire plein de hauteur n → O(2ⁿ) nœuds.
• Récursion en éventail (permutations) : n·(n−1)·… = O(n!) nœuds.

4.3 Formule générale

Complexité temps  = nombre de nœuds × coût par nœud
Complexité mémoire = profondeur maximale × taille d'une frame

---

Partie V — Backtracking : le principe

5.1 Définition

Le backtracking est une technique de recherche systématique qui explore l'espace des solutions par essais successifs, et qui revient en arrière (backtrack) dès qu'une branche ne peut plus mener à une solution valide.

C'est un DFS sur l'arbre de décision.

5.2 Les 3 ingrédients

5.3 Structure canonique

def backtrack(candidat, etat):
    if objectif_atteint(candidat):
        enregistrer_solution(candidat)
        return
    for option in choix(candidat):
        if contrainte_respectee(option, etat):
            faire_le_choix(option)          # essayer
            backtrack(candidat + [option], etat)
            annuler_le_choix(option)        # revenir en arrière

Le principe choisir → explorer → dés-choisir (make / recurse / unmake) est le squelette de tout backtracking.

5.4 Pruning (élagage)

Le pruning consiste à couper des branches avant même de les explorer, car on prouve qu'elles ne peuvent pas mener à une solution.

• Pruning par contrainte : on vérifie la contrainte avant de récurser.
• Pruning par borne : si une branche ne peut pas améliorer la meilleure solution trouvée → couper (branch & bound, Partie VIII).
• Pruning par symétrie : éliminer les solutions équivalentes par rotation/permutation.

---

Partie VI — Problèmes classiques

6.1 N-Queens

Placer n reines sur un échiquier n×n sans qu'aucune ne s'attaque.

def solve_n_queens(n: int) -> list[list[int]]:
    solutions = []
    cols = set(); diag1 = set(); diag2 = set()

    def backtrack(row, placement):
        if row == n:
            solutions.append(placement[:])
            return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue                      # PRUNING par contrainte
            cols.add(col); diag1.add(row - col); diag2.add(row + col)
            placement.append(col)
            backtrack(row + 1, placement)
            placement.pop()                   # backtrack
            cols.discard(col); diag1.discard(row - col); diag2.discard(row + col)

    backtrack(0, [])
    return solutions

• diag1 = row - col identifie la diagonale ↘ (constante sur une diagonale).
• diag2 = row + col identifie la diagonale ↙.
• Complexité : moins que O(n!) grâce au pruning ; nombre de solutions pour n=8 → 92.

6.2 Sudoku

• Choix : pour chaque case vide, une valeur de 1 à 9.
• Contraintes : pas de doublon dans la ligne, la colonne, ni le bloc 3×3.
• Objectif : grille complète.
• Pruning : on ne teste une valeur que si elle respecte les 3 contraintes (vérification O(1) avec des bitmasks ou des tableaux de booléens).

Complexité naïve : 9^(81)  (astronomique)
Avec pruning : résolution typique en < 1 ms sur grille standard

6.3 Word Search

Dans une grille de lettres, trouver un mot en se déplaçant 4 directions.

• Choix : les 4 voisins.
• Contraintes : dans les bornes, lettre correspondante, case non visitée.
• Objectif : atteindre la dernière lettre du mot.
• Pruning : test de contiguïté lettre par lettre ; backtracking sur le tableau de visite (marquer → explorer → dé-marquer).

6.4 Rat in a Maze

Un rat part de (0,0) et doit atteindre (n−1,n−1) dans un labyrinthe binaire (1 = libre, 0 = mur).

def rat_in_maze(grid):
    n = len(grid)
    path, result = [], []
    dirs = [(1, 0, 'D'), (0, 1, 'R'), (-1, 0, 'U'), (0, -1, 'L')]

    def dfs(x, y):
        if x == n - 1 and y == n - 1:
            result.append("".join(path))
            return
        for dx, dy, d in dirs:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 1:
                grid[nx][ny] = 0              # marquer
                path.append(d)
                dfs(nx, ny)
                path.pop()                    # dés-marquer (backtrack)
                grid[nx][ny] = 1

    if grid[0][0] == 1:
        grid[0][0] = 0
        dfs(0, 0)
    return result

---

Partie VII — Énumération combinatoire

7.1 Subsets (2ⁿ)

def subsets(nums):
    result = []
    def backtrack(start, courant):
        result.append(courant[:])
        for i in range(start, len(nums)):
            courant.append(nums[i])
            backtrack(i + 1, courant)
            courant.pop()
    backtrack(0, [])
    return result

7.2 Permutations (n!)

def permutations(nums):
    result = []
    def backtrack(courant):
        if len(courant) == len(nums):
            result.append(courant[:])
            return
        for x in nums:
            if x in courant:     # contrainte de non-répétition (O(n), à optimiser)
                continue
            courant.append(x)
            backtrack(courant)
            courant.pop()
    backtrack([])
    return result

Astuce d'optimisation : marquer les éléments visités dans un tableau de booléens → coût O(1) par test.

7.3 Combinations C(n, k)

def combinaisons(n, k):
    result = []
    def backtrack(start, courant):
        if len(courant) == k:
            result.append(courant[:])
            return
        for i in range(start, n + 1):
            courant.append(i)
            backtrack(i + 1, courant)   # ordre croissant → pas de doublon
            courant.pop()
    backtrack(1, [])
    return result

7.4 Récapitulatif des tailles

---

Partie VIII — Branch & Bound

8.1 Principe

Le branch & bound (B&B) est un backtracking pour problèmes d'optimisation (maximiser/minimiser). Il ajoute :

1. Branch : subdivision de l'espace en sous-problèmes (comme le backtracking).
2. Bound : calcul d'une borne (heuristique) sur la qualité de la meilleure solution possible dans une branche.

8.2 Règle de coupure

Si borne(noeud) est pire que la meilleure solution courante (best_so_far)
    alors on COUPE ce nœud (pruning par borne)

Pour un problème de minimisation : si la borne inférieure LB(noeud) ≥ best_so_far → inutile de poursuivre.

8.3 Exemple : Knapsack 0/1 (aperçu, chapitre 10)

• B&B : on parcourt les objets, à chaque nœud on calcule une borne supérieure (fractional knapsack relâché = remplir le sac avec l'objet suivant à fraction).
• Si valeur_relaxee < best_so_far → couper.
• Résultat : beaucoup plus efficace que l'énumération naïve pour de grandes instances.

8.4 Exemple : problème du voyageur de commerce (TSP)

• Borne : longueur du MST des villes restantes + coût pour y entrer.
• Si cout_partiel + borne ≥ best_so_far → couper.

---

Partie IX — Backtracking vs DP vs Greedy

Diagramme en cours de génération...

Règle de décision :

1. Si le problème a des sous-problèmes qui se recouvrent → DP.
2. Sinon, si un choix glouton est prouvablement optimal → Greedy.
3. Sinon, si l'espace est petit ou élagable → Backtracking / B&B.
4. Si l'espace est immense → heuristique / approximation (négociation entre qualité et temps).

---

Partie X — Visualisation et debug

10.1 Traçage manuel

def fib_trace(n, prof=0):
    print("  " * prof + f"fib({n})")
    if n < 2: return n
    return fib_trace(n-1, prof+1) + fib_trace(n-2, prof+1)

10.2 Outils

• Python : trace module, ou dessiner avec graphviz/pygraphviz.
• gdb / rr : inspecter la pile d'appels.
• VSCode / PyCharm : breakpoints sur les frames récursives.
• Mermaid / draw.io : schémas de l'arbre d'appels.

10.3 Anti-patterns courants

---

Résumé des complexités

---

Check-list de maîtrise

• Je sais écrire un cas de base et une relation de récurrence.
• Je sais dessiner l'arbre de récursion et compter ses nœuds.
• Je sais transformer une fonction en tail recursion.
• Je sais identifier choix / contraintes / objectif pour un problème donné.
• Je sais implémenter make / recurse / unmake proprement.
• Je sais élaguer par contrainte et par borne.
• Je sais choisir entre backtracking, DP et greedy.
• J'ai implémenté N-Queens et Sudoku dans au moins un langage.