🔄 La Récursivité

Une fonction est dite récursive si elle s'appelle elle-même dans sa propre définition. C'est un concept puissant pour résoudre des problèmes qui peuvent être décomposés en sous-problèmes identiques plus petits.

1. Anatomie d'une fonction récursive

Pour qu'une fonction récursive fonctionne correctement (et ne tourne pas à l'infini 💥), elle doit impérativement comporter deux parties :

1. Le Cas de Base (Condition d'arrêt) : C'est la situation simple où la fonction peut répondre directement sans s'appeler elle-même. C'est ce qui arrête la récursion.
2. L'Appel Récursif : La fonction s'appelle elle-même avec des arguments qui la rapprochent du cas de base.

Exemple : La Factorielle

La factorielle de $n$ ($n!$) est le produit des nombres de 1 à $n$.

• Mathématiquement :
  • $0! = 1$
  • $n! = n \times (n-1)!$ pour $n > 0$

def factorielle(n):
    # 1. Cas de base
    if n == 0:
        return 1
    # 2. Appel récursif
    else:
        return n * factorielle(n - 1)

2. La Pile d'Exécution (Call Stack)

Comment l'ordinateur gère-t-il cela ? Il utilise une pile. Imaginez une pile d'assiettes. À chaque appel de fonction, on ajoute une assiette (un contexte d'exécution) sur la pile. Quand une fonction se termine (return), on retire l'assiette.

Exemple pour factorielle(3) :

1. Appel factorielle(3) : besoin de factorielle(2) -> Empile
2. Appel factorielle(2) : besoin de factorielle(1) -> Empile
3. Appel factorielle(1) : besoin de factorielle(0) -> Empile
4. Appel factorielle(0) : renvoie 1 (Cas de base !) -> Dépile
5. Reprise factorielle(1) : calcule 1 * 1 = 1 -> Dépile
6. Reprise factorielle(2) : calcule 2 * 1 = 2 -> Dépile
7. Reprise factorielle(3) : calcule 3 * 2 = 6 -> Dépile
8. Résultat final : 6.

⚠️ Stack Overflow : Si vous oubliez le cas de base ou si la récursion est trop profonde (par défaut 1000 en Python), la pile déborde et le programme plante (RecursionError).

3. Récursif vs Itératif

Tout programme récursif peut être écrit de manière itérative (avec des boucles for ou while), et inversement.

• Itératif : Souvent plus efficace en mémoire (pas d'empilement).
• Récursif : Souvent plus élégant et plus simple à écrire pour certains problèmes (arbres, graphes, tours de Hanoï).