1. Définition et principe de récursion

Une fonction est qualifiée de récursive lorsqu’elle s’appelle elle-même au cours de son exécution afin de résoudre une instance plus petite du même problème. Ce paradigme traduit naturellement les définitions inductives courantes en mathématiques.

Toute fonction récursive correcte repose impérativement sur deux piliers :

  • Le cas de base (condition d’arrêt) : condition élémentaire résolue trivialement sans aucun rappel récursif.
  • Le cas inductif (pas de réduction) : étape qui décompose le problème actuel en une instance strictement plus proche du cas de base.

2. La pile d’appels (Call Stack) sous le capot

Chaque appel de fonction empile un bloc d’activation (stack frame) contenant ses variables locales et son adresse de retour sur la pile d’exécution système (Call Stack). Lorsque le cas de base est atteint, la pile se dépile en sens inverse (LIFO) en propageant les résultats partiels :

def compte_a_rebours(n: int) -> None:
    # 1. Cas de base
    if n <= 0:
        print("Décollage réussi !")
        return
    # 2. Action locale
    print(f"T-moins : {n}")
    # 3. Appel récursif avec réduction
    compte_a_rebours(n - 1)

compte_a_rebours(3)

3. Le piège du débordement de pile (RecursionError)

Si la condition d'arrêt est omise ou incorrecte, la pile s'accumule jusqu'à saturer la mémoire allouée. Python protège l'interpréteur par une limite de récursion (par défaut 1000 appels), déclenchant une exception RecursionError: maximum recursion depth exceeded.

Synthèse pédagogique : La récursivité apporte une élégance conceptuelle remarquable pour traiter des structures arborescentes ; assurez-vous cependant que chaque appel converge inexorablement vers le cas de base.

PreviousNext