Récursivité

Récursivité#

Hide code cell source

 
import matplotlib.pyplot as plt
import matplotlib.patches as patches
import numpy as np
import seaborn as sns
from functools import lru_cache, cache
import sys

sns.set_theme(style="whitegrid", palette="muted", font_scale=1.1)

Principe de la récursivité#

La récursivité est une technique de conception d’algorithmes dans laquelle une fonction résout un problème en se rappelant elle-même sur des instances plus petites du même problème. C’est l’application directe du principe de diviser pour régner : si l’on peut exprimer la solution d’un problème en fonction de solutions à des sous-problèmes de même nature, alors la récursivité offre une formulation naturelle et élégante.

La récursivité repose sur deux composantes obligatoires.

Définition 19 (Structure d’une fonction récursive)

Toute fonction récursive correcte doit comporter :

  1. Un ou plusieurs cas de base (base cases) : des instances du problème si petites qu’on peut les résoudre directement, sans appel récursif. Sans cas de base, la récursion est infinie.

  2. Un ou plusieurs cas récursifs (recursive cases) : des cas où la fonction s’appelle elle-même sur une instance strictement plus petite, se rapprochant ainsi du cas de base. La décroissance de la taille garantit la terminaison.

Remarque 6

Le lien entre récursivité et induction mathématique est profond. Une preuve par récurrence prouve une propriété \(P(n)\) en montrant :

  • Base : \(P(0)\) est vraie.

  • Hérédité : \(P(n-1)\) vraie implique \(P(n)\) vraie.

Une fonction récursive calcule \(f(n)\) en supposant que \(f(n-1)\) est déjà calculé correctement. Prouver la correction d’une fonction récursive revient exactement à faire une récurrence : on suppose que les appels récursifs retournent la bonne valeur (hypothèse d’induction), et on montre que l’appel courant retourne la bonne valeur.

La pile d’appels#

Pour comprendre comment s’exécute une fonction récursive, il faut comprendre la pile d’appels (call stack).

Définition 20 (Pile d’appels)

La pile d’appels est une structure de données en mémoire qui mémorise les appels de fonctions en cours d’exécution. Chaque appel de fonction crée un cadre de pile (stack frame) contenant :

  • les paramètres de la fonction,

  • les variables locales,

  • l’adresse de retour (où reprendre l’exécution après retour).

Lors d’un appel récursif, un nouveau cadre est empilé par-dessus le cadre courant. Lorsqu’une fonction retourne, son cadre est dépilé et l’exécution reprend dans le cadre précédent.

La conséquence directe est que chaque niveau de récursion occupe de l’espace en mémoire. Pour une récursion de profondeur \(d\), la pile occupe \(O(d)\) cadres simultanément. En Python, la profondeur maximale est limitée par défaut.

import sys

print(f"Limite de récursion par défaut : {sys.getrecursionlimit()}")

# On peut l'augmenter, mais avec prudence :
# sys.setrecursionlimit(10_000)

def profondeur_de_recursion_actuelle():
    """Renvoie une estimation de la profondeur de récursion actuelle."""
    frame = sys._getframe()
    depth = 0
    while frame is not None:
        frame = frame.f_back
        depth += 1
    return depth

print(f"Profondeur de pile actuelle : {profondeur_de_recursion_actuelle()}")

Limite de récursion par défaut : 3000
Profondeur de pile actuelle : 23

Exemples classiques#

Factorielle#

La factorielle est l’exemple canonique de la récursivité. Sa définition mathématique est elle-même récursive.

Définition 21 (Factorielle)

La factorielle de \(n \in \mathbb{N}\) est définie par :

\[\begin{split}n! = \begin{cases} 1 & \text{si } n = 0 \\ n \cdot (n-1)! & \text{si } n \geq 1 \end{cases}\end{split}\]

Cette définition a exactement la forme d’une fonction récursive : un cas de base (\(0! = 1\)) et un cas récursif (\(n! = n \cdot (n-1)!\)).

def factorielle_recursive(n: int) -> int:
    """
    Factorielle récursive.
    Complexité : O(n) en temps, O(n) en espace (pile d'appels de profondeur n).
    """
    if n < 0:
        raise ValueError("La factorielle n'est définie que pour les entiers positifs.")
    if n == 0:  # cas de base
        return 1
    return n * factorielle_recursive(n - 1)  # cas récursif


def factorielle_iterative(n: int) -> int:
    """
    Factorielle itérative.
    Complexité : O(n) en temps, O(1) en espace.
    """
    if n < 0:
        raise ValueError("La factorielle n'est définie que pour les entiers positifs.")
    resultat = 1
    for i in range(2, n + 1):
        resultat *= i
    return resultat


# Tests
for n in range(10):
    r = factorielle_recursive(n)
    i = factorielle_iterative(n)
    assert r == i, f"Divergence pour n={n}: {r} vs {i}"
    print(f"{n}! = {r}")

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880

Suite de Fibonacci#

La suite de Fibonacci illustre les dangers de la récursivité naïve : une définition mathématique élégante peut donner naissance à un algorithme exponentiellement lent.

Définition 22 (Suite de Fibonacci)

La suite de Fibonacci \((F_n)_{n \geq 0}\) est définie par :

\[\begin{split}F_n = \begin{cases} 0 & \text{si } n = 0 \\ 1 & \text{si } n = 1 \\ F_{n-1} + F_{n-2} & \text{si } n \geq 2 \end{cases}\end{split}\]

Les premiers termes sont : \(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \ldots\)

def fibonacci_naif(n: int) -> int:
    """
    Fibonacci naïf : deux appels récursifs par appel.
    Complexité : O(2^n) en temps, O(n) en espace (hauteur de la pile).

    ATTENTION : inutilisable pour n > 35 environ.
    """
    if n <= 1:
        return n
    return fibonacci_naif(n - 1) + fibonacci_naif(n - 2)


def fibonacci_iteratif(n: int) -> int:
    """
    Fibonacci itératif : O(n) en temps, O(1) en espace.
    """
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b


# Comptage des appels pour fibonacci_naif
appels = [0]

def fibonacci_compte(n: int) -> int:
    appels[0] += 1
    if n <= 1:
        return n
    return fibonacci_compte(n - 1) + fibonacci_compte(n - 2)


print(f"{'n':>4} {'F(n)':>10} {'Appels (naïf)':>15} {'Appels théoriques (~2^n)':>25}")
print("-" * 58)
for n in range(1, 20):
    appels[0] = 0
    val = fibonacci_compte(n)
    print(f"{n:>4} {val:>10} {appels[0]:>15} {2**n:>25,}")

   n       F(n)   Appels (naïf)  Appels théoriques (~2^n)
----------------------------------------------------------
   1          1               1                         2
   2          1               3                         4
   3          2               5                         8
   4          3               9                        16
   5          5              15                        32
   6          8              25                        64
   7         13              41                       128
   8         21              67                       256
   9         34             109                       512
  10         55             177                     1,024
  11         89             287                     2,048
  12        144             465                     4,096
  13        233             753                     8,192
  14        377            1219                    16,384
  15        610            1973                    32,768
  16        987            3193                    65,536
  17       1597            5167                   131,072
  18       2584            8361                   262,144
  19       4181           13529                   524,288

Tours de Hanoï#

Les tours de Hanoï constituent l’exemple le plus pur du paradigme récursif : le problème n’a pas de solution itérative simple et naturelle.

Définition 23 (Problème des tours de Hanoï)

Le problème des tours de Hanoï consiste à déplacer \(n\) disques de tailles décroissantes d’une tige source vers une tige destination, en utilisant une tige auxiliaire, selon les règles suivantes :

  • On ne peut déplacer qu’un seul disque à la fois (le disque du dessus d’une tige).

  • Un disque ne peut jamais être posé sur un disque plus petit.

La solution récursive est : pour déplacer \(n\) disques de la tige source vers destination via auxiliaire :

  1. Déplacer les \(n-1\) disques supérieurs de source vers auxiliaire via destination.

  2. Déplacer le disque du bas de source vers destination.

  3. Déplacer les \(n-1\) disques de auxiliaire vers destination via source.

def hanoi(n: int, source: str, destination: str, auxiliaire: str,
          mouvements: list | None = None) -> list:
    """
    Résout les tours de Hanoï pour n disques.
    Retourne la liste des mouvements (source -> destination).
    Complexité : O(2^n) mouvements, O(n) en espace (pile).
    """
    if mouvements is None:
        mouvements = []
    if n == 1:
        mouvements.append((source, destination))
        return mouvements
    hanoi(n - 1, source, auxiliaire, destination, mouvements)
    mouvements.append((source, destination))
    hanoi(n - 1, auxiliaire, destination, source, mouvements)
    return mouvements


for n in range(1, 7):
    mvts = hanoi(n, 'A', 'C', 'B')
    print(f"n={n} : {len(mvts):>3} mouvements (2^n - 1 = {2**n - 1})")

print("\nDétail pour n=3 :")
for i, (src, dst) in enumerate(hanoi(3, 'A', 'C', 'B'), 1):
    print(f"  Mouvement {i:2} : {src} → {dst}")

n=1 :   1 mouvements (2^n - 1 = 1)
n=2 :   3 mouvements (2^n - 1 = 3)
n=3 :   7 mouvements (2^n - 1 = 7)
n=4 :  15 mouvements (2^n - 1 = 15)
n=5 :  31 mouvements (2^n - 1 = 31)
n=6 :  63 mouvements (2^n - 1 = 63)

Détail pour n=3 :
  Mouvement  1 : A → C
  Mouvement  2 : A → B
  Mouvement  3 : C → B
  Mouvement  4 : A → C
  Mouvement  5 : B → A
  Mouvement  6 : B → C
  Mouvement  7 : A → C

Remarque 7

Le nombre minimal de mouvements pour déplacer \(n\) disques est \(2^n - 1\), ce qui se prouve par récurrence. Pour \(n = 64\) disques (la légende des moines), cela fait \(2^{64} - 1 \approx 1,8 \times 10^{19}\) mouvements. À raison d’un mouvement par seconde, cela prendrait environ 585 milliards d’années — soit 42 fois l’âge de l’univers.

Récursion terminale#

Définition 24 (Récursion terminale (tail recursion))

Un appel récursif est dit terminal (tail call) si c’est la dernière opération effectuée par la fonction : la valeur retournée par l’appel récursif est immédiatement retournée sans calcul supplémentaire. Une fonction entièrement structurée sur des appels terminaux est dite récursive terminale (tail recursive).

Exemple 8 (Factorielle récursive terminale)

La factorielle récursive classique n’est pas terminale : après l’appel récursif factorielle(n-1), on effectue encore une multiplication par n. Pour la rendre terminale, on introduit un accumulateur :

def factorielle_terminale(n: int, accumulateur: int = 1) -> int:
    if n == 0:
        return accumulateur
    return factorielle_terminale(n - 1, n * accumulateur)  # appel terminal

Ici, l’appel récursif est la dernière chose que fait la fonction. La valeur finale est portée par l’accumulateur.

Remarque 8

En théorie, un compilateur reconnaissant les appels terminaux peut les optimiser en une simple itération (tail call optimization, TCO) : au lieu d’empiler un nouveau cadre, il réutilise le cadre courant. Cela transforme une récursion de profondeur \(O(n)\) en espace en une boucle en espace \(O(1)\).

Cependant, Python n’implémente pas cette optimisation, et ce de façon délibérée. Guido van Rossum a exprimé sa préférence pour que les traces de pile restent lisibles lors du débogage. En Python, une récursion terminale présente les mêmes risques de dépassement de pile qu’une récursion non terminale. Pour les programmes nécessitant une très grande profondeur, il faut toujours préférer la version itérative.

Mémoïsation#

La mémoïsation est la technique qui consiste à mémoriser les résultats déjà calculés pour éviter de les recalculer. Elle transforme un algorithme récursif de complexité exponentielle en algorithme polynomial.

Définition 25 (Mémoïsation)

La mémoïsation (memoization) est une technique d’optimisation qui consiste à stocker dans un cache les résultats des appels de fonctions pour des arguments donnés, de manière à ne pas recalculer un résultat déjà obtenu. La mémoïsation est applicable lorsque la fonction est pure : ses sorties dépendent uniquement de ses entrées (pas d’effets de bord).

from functools import lru_cache, cache

# Mémoïsation manuelle avec un dictionnaire
def fibonacci_memo_manuel(n: int, memo: dict | None = None) -> int:
    """
    Fibonacci avec mémoïsation manuelle.
    Complexité : O(n) en temps et en espace.
    """
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_memo_manuel(n - 1, memo) + fibonacci_memo_manuel(n - 2, memo)
    return memo[n]


# Mémoïsation avec functools.lru_cache
@lru_cache(maxsize=None)
def fibonacci_lru(n: int) -> int:
    """
    Fibonacci avec @lru_cache. Syntaxe plus concise.
    maxsize=None signifie un cache illimité.
    """
    if n <= 1:
        return n
    return fibonacci_lru(n - 1) + fibonacci_lru(n - 2)


# Mémoïsation avec @cache (Python 3.9+, équivalent à lru_cache(maxsize=None))
@cache
def fibonacci_cache(n: int) -> int:
    """Fibonacci avec @cache (Python 3.9+)."""
    if n <= 1:
        return n
    return fibonacci_cache(n - 1) + fibonacci_cache(n - 2)


# Comparaison
import timeit

n_test = 35
print(f"Calcul de F({n_test}) :")

t_naif = timeit.timeit(lambda: fibonacci_naif(n_test), number=1)
t_memo = timeit.timeit(lambda: fibonacci_memo_manuel(n_test), number=100) / 100
t_lru  = timeit.timeit(lambda: fibonacci_lru(n_test), number=100) / 100

print(f"  Naïf O(2^n)    : {t_naif:.4f} s")
print(f"  Mémo manuelle  : {t_memo:.8f} s")
print(f"  @lru_cache     : {t_lru:.8f} s")
print(f"  Rapport naïf/mémo : {t_naif/t_memo:.0f}x")

print(f"\nF(50) = {fibonacci_lru(50)}")
print(f"F(100) = {fibonacci_lru(100)}")
print(f"Taille du cache lru : {fibonacci_lru.cache_info()}")

Calcul de F(35) :

  Naïf O(2^n)    : 2.4540 s
  Mémo manuelle  : 0.00001205 s
  @lru_cache     : 0.00000040 s
  Rapport naïf/mémo : 203719x

F(50) = 12586269025
F(100) = 354224848179261915075
Taille du cache lru : CacheInfo(hits=199, misses=101, maxsize=None, currsize=101)

Récursion mutuelle#

Définition 26 (Récursion mutuelle)

Deux fonctions \(f\) et \(g\) sont en récursion mutuelle si \(f\) s’appelle \(g\) et \(g\) s’appelle \(f\). Plus généralement, un ensemble de fonctions \(\{f_1, \ldots, f_k\}\) est en récursion mutuelle si leurs graphes d’appel forment un cycle.

def est_pair(n: int) -> bool:
    """
    Détermine si n est pair par récursion mutuelle.
    Exemple pédagogique — non recommandé en pratique.
    """
    if n == 0:
        return True
    return est_impair(n - 1)


def est_impair(n: int) -> bool:
    """Détermine si n est impair par récursion mutuelle."""
    if n == 0:
        return False
    return est_pair(n - 1)


# Test sur de petits entiers (profondeur de récursion = n)
for n in range(10):
    assert est_pair(n) == (n % 2 == 0), f"Erreur pour n={n}"
print("Tests de récursion mutuelle réussis pour n = 0 à 9.")


# Exemple plus sérieux : la suite de Hofstadter (récursion mutuelle non triviale)
@cache
def hofstadter_f(n: int) -> int:
    """Suite de Hofstadter F : F(n) = n - M(F(n-1)) pour n > 0, F(0) = 1."""
    if n == 0:
        return 1
    return n - hofstadter_m(hofstadter_f(n - 1))


@cache
def hofstadter_m(n: int) -> int:
    """Suite de Hofstadter M : M(n) = n - F(M(n-1)) pour n > 0, M(0) = 0."""
    if n == 0:
        return 0
    return n - hofstadter_f(hofstadter_m(n - 1))


print("\nSuite de Hofstadter F(n) :")
print([hofstadter_f(n) for n in range(20)])
print("Suite de Hofstadter M(n) :")
print([hofstadter_m(n) for n in range(20)])

Tests de récursion mutuelle réussis pour n = 0 à 9.

Suite de Hofstadter F(n) :
[1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12]
Suite de Hofstadter M(n) :
[0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12]

Quand préférer l’itération à la récursion ?#

La récursivité est un outil puissant, mais elle n’est pas toujours la meilleure approche en Python.

Remarque 9

Préférer l’itération à la récursion dans les cas suivants :

  1. Profondeur potentiellement grande. Si la profondeur de récursion peut dépasser quelques milliers, le risque de RecursionError est réel. L’itération ne souffre pas de cette limitation.

  2. Récursion linéaire simple. Factorielle, somme d’un tableau, maximum : toutes ces fonctions se transforment trivialement en boucle, avec une complexité spatiale réduite de \(O(n)\) à \(O(1)\).

  3. Performance critique. En Python, chaque appel de fonction engendre un coût de création de cadre de pile non négligeable. Pour une récursion profonde sur des données volumineuses, la version itérative peut être plusieurs fois plus rapide.

  4. Langage sans TCO. Puisque Python n’optimise pas les appels terminaux, les récursions profondes se traduisent toujours par une pile proportionnelle à la profondeur.

Préférer la récursion dans les cas suivants :

  1. Structure naturellement récursive. Arbres, graphes, expressions arithmétiques : leur structure est récursive, et l’algorithme récursif est souvent le plus lisible et le plus facile à prouver correct.

  2. Diviser pour régner. Tri fusion, recherche binaire, transformation de Fourier rapide (FFT) : ces algorithmes s’expriment naturellement comme une récursion avec une réduction géométrique de la taille.

  3. Profondeur logarithmique. Si la profondeur est \(O(\log n)\), le risque de dépassement est négligeable (\(\log_2(10^9) < 30\)), et la version récursive est souvent plus claire.

Implémentation Python et Rust#

# Factorielle et Fibonacci : versions itératives vs récursives
import time

def benchmark_fibonacci():
    """Compare les différentes implémentations de Fibonacci."""
    valeurs_n = list(range(0, 36))

    # Fibonacci itératif
    def fib_iter(n):
        if n <= 1:
            return n
        a, b = 0, 1
        for _ in range(n - 1):
            a, b = b, a + b
        return b

    # Fibonacci avec mémoïsation
    @cache
    def fib_memo(n):
        if n <= 1:
            return n
        return fib_memo(n - 1) + fib_memo(n - 2)

    print(f"{'n':>4} {'Itératif':>12} {'Mémoïsé':>12}")
    print("-" * 30)
    for n in valeurs_n:
        assert fib_iter(n) == fib_memo(n)
        if n <= 15:
            print(f"{n:>4} {fib_iter(n):>12} {fib_memo(n):>12}")
    print("  ...")

benchmark_fibonacci()

   n     Itératif      Mémoïsé
------------------------------
   0            0            0
   1            1            1
   2            1            1
   3            2            2
   4            3            3
   5            5            5
   6            8            8
   7           13           13
   8           21           21
   9           34           34
  10           55           55
  11           89           89
  12          144          144
  13          233          233
  14          377          377
  15          610          610
  ...

Implémentation Rust#

/// Factorielle itérative en Rust.
/// Utilise u128 pour supporter de grands nombres (jusqu'à 34!).
fn factorielle_iterative(n: u32) -> u128 {
    (1..=n as u128).product()
}

/// Factorielle récursive en Rust.
fn factorielle_recursive(n: u32) -> u128 {
    if n == 0 {
        1
    } else {
        n as u128 * factorielle_recursive(n - 1)
    }
}

/// Fibonacci itératif : O(n) temps, O(1) espace.
fn fibonacci_iteratif(n: u64) -> u128 {
    if n <= 1 {
        return n as u128;
    }
    let (mut a, mut b) = (0u128, 1u128);
    for _ in 1..n {
        (a, b) = (b, a + b);
    }
    b
}

/// Fibonacci mémoïsé avec un vecteur.
/// Cette version itérative avec cache est équivalente à la mémoïsation récursive.
fn fibonacci_memo(n: usize) -> u128 {
    if n <= 1 {
        return n as u128;
    }
    let mut memo = vec![0u128; n + 1];
    memo[0] = 0;
    memo[1] = 1;
    for i in 2..=n {
        memo[i] = memo[i - 1] + memo[i - 2];
    }
    memo[n]
}

/// Tours de Hanoï récursives.
fn hanoi(n: u32, source: char, destination: char, auxiliaire: char) -> Vec<(char, char)> {
    if n == 0 {
        return vec![];
    }
    let mut mouvements = hanoi(n - 1, source, auxiliaire, destination);
    mouvements.push((source, destination));
    let mut reste = hanoi(n - 1, auxiliaire, destination, source);
    mouvements.append(&mut reste);
    mouvements
}

fn main() {
    // Factorielle
    for n in 0..=20u32 {
        assert_eq!(factorielle_iterative(n), factorielle_recursive(n));
    }
    println!("10! = {}", factorielle_iterative(10));
    println!("20! = {}", factorielle_iterative(20));

    // Fibonacci
    for n in 0..=50u64 {
        assert_eq!(fibonacci_iteratif(n), fibonacci_memo(n as usize));
    }
    println!("F(50) = {}", fibonacci_iteratif(50));

    // Hanoï
    let mouvements = hanoi(3, 'A', 'C', 'B');
    println!("Hanoï(3) : {} mouvements", mouvements.len());
    for (src, dst) in &mouvements {
        println!("  {} → {}", src, dst);
    }
}

Visualisation : arbre des appels de Fibonacci#

Hide code cell source

 
def construire_arbre_fibonacci(n: int) -> dict:
    """
    Construit l'arbre des appels récursifs de Fibonacci(n).
    Retourne un dictionnaire de nœuds avec positions et arêtes.
    """
    noeuds = {}
    aretes = []
    compteur = [0]

    def fibonacci_trace(n, profondeur, position_x):
        id_noeud = compteur[0]
        compteur[0] += 1
        noeuds[id_noeud] = {
            'n': n,
            'profondeur': profondeur,
            'x': position_x,
            'y': -profondeur,
        }
        if n <= 1:
            return id_noeud

        # Espacement dépendant de la profondeur
        ecart = 2 ** (4 - profondeur) / 2.0

        id_gauche = fibonacci_trace(n - 1, profondeur + 1, position_x - ecart)
        aretes.append((id_noeud, id_gauche))

        id_droite = fibonacci_trace(n - 2, profondeur + 1, position_x + ecart)
        aretes.append((id_noeud, id_droite))

        return id_noeud

    fibonacci_trace(n, 0, 0)
    return noeuds, aretes


fig, axes = plt.subplots(1, 2, figsize=(16, 8))

# --- Graphique 1 : arbre des appels ---
ax = axes[0]
n_arbre = 5
noeuds, aretes = construire_arbre_fibonacci(n_arbre)

# Palette de couleurs par profondeur
profondeur_max = max(v['profondeur'] for v in noeuds.values())
cmap = plt.colormaps['Blues']

# Arêtes
for (id1, id2) in aretes:
    x1, y1 = noeuds[id1]['x'], noeuds[id1]['y']
    x2, y2 = noeuds[id2]['x'], noeuds[id2]['y']
    ax.plot([x1, x2], [y1, y2], color='#aaaaaa', lw=1.2, zorder=1)

# Nœuds
# Compter les appels redondants
comptage_n = {}
for v in noeuds.values():
    comptage_n[v['n']] = comptage_n.get(v['n'], 0) + 1

for id_noeud, v in noeuds.items():
    profondeur = v['profondeur']
    couleur = cmap(0.3 + 0.7 * profondeur / profondeur_max)
    cercle = plt.Circle((v['x'], v['y']), 0.28,
                         color=couleur, zorder=3)
    ax.add_patch(cercle)
    ax.text(v['x'], v['y'], f"F({v['n']})",
            ha='center', va='center', fontsize=7,
            fontweight='bold', color='white', zorder=4)

ax.set_xlim(-9, 9)
ax.set_ylim(-n_arbre - 0.8, 0.8)
ax.set_aspect('equal')
ax.axis('off')
ax.set_title(f'Arbre des appels récursifs de Fibonacci({n_arbre})',
             fontsize=13, fontweight='bold')

# Annotation du nombre d'appels
total = len(noeuds)
ax.text(0, -n_arbre - 0.5,
        f'Total : {total} appels pour F({n_arbre})\n(comparer avec F({n_arbre}+1)={fibonacci_naif(n_arbre+1)} appels pour F({n_arbre+1}))',
        ha='center', va='center', fontsize=9, color='#555555',
        style='italic',
        bbox=dict(boxstyle='round,pad=0.3', facecolor='#ffeeba', alpha=0.8))

# --- Graphique 2 : comparaison du nombre d'appels ---
ax2 = axes[1]

ns = list(range(1, 30))
appels_naif = []
appels_memo = []

for n in ns:
    # Compter les appels de fibonacci_naif
    c = [0]
    def fib_c(k):
        c[0] += 1
        if k <= 1:
            return k
        return fib_c(k - 1) + fib_c(k - 2)
    fib_c(n)
    appels_naif.append(c[0])

    # Fibonacci mémoïsé : exactement n-1 nouveaux appels + le premier
    appels_memo.append(max(1, n))

ax2.semilogy(ns, appels_naif, 'o-', color='#e74c3c',
             label='Récursif naïf O(2ⁿ)', linewidth=2, markersize=5)
ax2.semilogy(ns, appels_memo, 's-', color='#2ecc71',
             label='Avec mémoïsation O(n)', linewidth=2, markersize=5)
ax2.set_xlabel('n', fontsize=12)
ax2.set_ylabel('Nombre d\'appels (échelle log)', fontsize=12)
ax2.set_title('Impact de la mémoïsation sur Fibonacci', fontsize=13,
              fontweight='bold')
ax2.legend(fontsize=11)

plt.suptitle('Récursivité : appels et mémoïsation', fontsize=15,
             fontweight='bold', y=1.01)
plt.tight_layout()
plt.show()
_images/6b3dd07f203ebd9b801c8e8cc8b330a1a0fdfdad0005d0767988d21df3963ffd.png

Résumé#

Dans ce chapitre, nous avons exploré en profondeur la récursivité :

  • Une fonction récursive comporte toujours un cas de base (résolution directe) et un cas récursif (appel sur une instance strictement plus petite). La preuve de correction se fait par récurrence structurelle.

  • La pile d’appels empile un cadre par niveau de récursion. La profondeur maximale en Python est de 1 000 par défaut (modifiable via sys.setrecursionlimit). Une récursion profonde risque un RecursionError.

  • La récursion naïve de Fibonacci est de complexité \(O(2^n)\) à cause des sous-problèmes recalculés. La mémoïsation (@lru_cache, @cache) la réduit à \(O(n)\) en mémorisant les résultats.

  • La récursion terminale place l’appel récursif en dernière position. Python ne l’optimise pas, contrairement à Haskell, Scheme ou Rust (dans certains cas). En pratique, pour les récursions profondes, on préfère l’itération.

  • La récursion mutuelle entre plusieurs fonctions est utile pour les grammaires formelles et certains problèmes de combinatoire.

  • Les tours de Hanoï illustrent un problème dont la solution récursive est naturelle et dont la complexité \(O(2^n)\) est optimale (le problème exige \(2^n - 1\) mouvements).

Dans le chapitre suivant, nous étudierons les premières structures de données linéaires : tableaux et listes chaînées, leurs propriétés mémoire, et les compromis entre accès et modification.

Contenu