Récursivité et pourquoi Python ne l'aime (pas) 🌀

Si lors d'un entretien on vous demande d'écrire une factorielle ou les nombres de Fibonacci par récursivité — écrivez. Mais si vous l'utilisez souvent en pratique...
Oui, la récursivité est conceptuellement belle, mathématiquement élégante, mais si on s'emballe, on peut faire planter la prod et saturer toute la RAM avec des frames de pile.

Analysons ce qui se passe sous le capot et pourquoi Python, contrairement aux langages fonctionnels, n'aime pas la récursivité.

1️⃣ Le prix à payer : la pile d'appels
Chaque appel de fonction n'est pas gratuit. Cela crée un nouveau stack frame en mémoire. Dans ce frame sont stockées les variables locales et l'adresse de retour.
Imaginez une poupée russe où chaque poupée suivante pèse autant que la précédente. En Python, ce "poids" pèse sur la RAM.
Une boucle while ou for utilise un seul bloc mémoire. La récursivité consomme de la mémoire linéairement (ou exponentiellement) proportionnellement à la profondeur d'appel.

2️⃣ Pourquoi il n'y a pas d'optimisation de la récursion terminale
Dans des langages comme Haskell ou C++, le compilateur est intelligent. Si l'appel récursif est la dernière action de la fonction (récursion terminale), il le remplace par un simple saut (GOTO), sans créer de nouveau frame. Cela s'appelle Tail Call Optimization (TCO).

En Python, il n'y a pas de TCO et il n'y en aura pas. Guido van Rossum (BDFL) est fondamentalement opposé au TCO en Python. L'argument est simple : « Nous voulons voir des tracebacks d'erreurs complets ». Si on réduit la pile, vous ne saurez jamais à quel niveau de récursion tout a planté.
C'est pourquoi la limite de 1000 appels (par défaut) n'est pas un bug, mais un garde-fou contre le débordement de pile. Peut-on l'augmenter via sys.setrecursionlimit ? Oui. Mais si vous en avez besoin, il y a 99% de chances que vous ayez fait une erreur d'architecture.

3️⃣ Quand la récursivité est un mal, et quand une nécessité ?
❌ Structures linéaires (par exemple, listes) : Calcul de factorielle, nombres de Fibonacci ou parcours de liste plate. Une boucle itérative while/for sera toujours plus rapide et plus économique en mémoire (mémoire O(1) contre O(N)).
✅ Structures ramifiées (arbres, graphes, dict imbriqués) : Analyse JSON, parcours de système de fichiers, arbre DOM ou algorithmes de type Divide and Conquer (QuickSort, MergeSort). Ici, la récursivité réduit la charge cognitive et rend le code lisible.

4️⃣ Remède contre les ralentissements : @lru_cache
Exemple classique de bêtise : le calcul de Fibonacci "à la brute". Complexité O(2^n). Cela signifie que pour calculer le 50e nombre, le programme mourra avant d'avoir fini.
Solution — Mémoïsation.
Le décorateur @functools.lru_cache met en cache les résultats des appels. Si la fonction a déjà été calculée avec cet argument, Python récupère simplement la valeur prête dans la table de hachage. Cela transforme l'horreur exponentielle en complexité linéaire O(N).

En résumé : Python n'est pas Haskell ou Lisp. Ici, la récursivité est un citoyen de seconde classe. Utilisez-la pour les arbres et les graphes, mais pour tout le reste, il y a les boucles.

#anatomie_de_python