La pile d'appels, Fibonacci, avantages et pièges

La pile d'appels, Fibonacci, avantages et pièges

Quand une fonction récursive s'exécute, chaque appel est empilé en mémoire dans ce qu'on appelle la pile d'appels : Python garde en mémoire l'état de chaque appel en attente (ses variables locales, l'endroit où reprendre le calcul), jusqu'à ce que l'appel le plus profond (le cas de base) renvoie sa valeur. Les résultats remontent alors la pile, un appel après l'autre, jusqu'au tout premier appel.

Un exemple plus complexe : la suite de Fibonacci, où chaque terme est la somme des deux précédents (0, 1, 1, 2, 3, 5, 8...) :

def fibonacci(n):
    if n <= 1:
        return n                                  # (cas de base)
    else:
        return fibonacci(n - 1) + fibonacci(n - 2) # (cas recursif, deux appels)

print(fibonacci(5))   # (affiche 5)

Ici, chaque appel en déclenche deux nouveaux, ce qui fait grandir très vite le nombre total d'appels : c'est un des pièges de la récursivité.

Avantages de la récursivité :

• un code souvent plus court et plus proche de la définition mathématique du problème,
• particulièrement adapté aux structures qui se définissent naturellement de façon récursive (arbres, dossiers imbriqués...).

Pièges à connaître :

• la récursion infinie : un cas de base manquant ou jamais atteint provoque une erreur RecursionError,
• le coût en mémoire et en temps : chaque appel occupe de la place dans la pile, et certaines fonctions (comme fibonacci ci-dessus) recalculent plusieurs fois les mêmes valeurs, ce qui peut devenir très lent pour de grands nombres.

En résumé, la récursivité est un outil puissant, à utiliser quand elle rend vraiment le code plus clair, mais jamais sans avoir vérifié qu'un cas de base existe et sera bien atteint.