Récursion contre itération : profondeur de pile, limites et quand convertir

Ce que c'est

Une fonction récursive résout un problème en s'appelant elle-même sur des instances plus petites ; chaque appel non terminé occupe une trame sur la pile d'appels. La pile est finie. Python impose une limite de récursion, lisible avec sys.getrecursionlimit(), que la documentation décrit comme empêchant une récursion infinie de faire déborder la pile C et de planter l'interpréteur ; la dépasser lève RecursionError. Le code natif est borné par la taille de pile du thread (la limite du thread principal est RLIMIT_STACK dans getrlimit(2)) ; la dépasser produit un défaut de segmentation, pas une exception. L'itération garde l'état dans des variables ou dans une pile ou une file explicite sur le tas, dont la taille est limitée par la mémoire plutôt que par une pile fixe.

Pourquoi c'est important

Une récursion dont la profondeur suit l'entrée est une surface de déni de service : un JSON profondément imbriqué, une arborescence de répertoires à des milliers de niveaux, une structure chaînée longue ou un analyseur de crochets imbriqués peuvent être plantés par une entrée conçue à cet effet. Ne pas présumer l'élimination des appels terminaux sauf si la spécification du langage la garantit ; la plupart des langages courants ne le font pas, si bien qu'une « boucle récursive terminale » consomme quand même une trame par itération.

Comment l'appliquer

• Réserver la récursion aux problèmes dont la profondeur est bornée par la structure, pas par la taille de l'entrée : arbres équilibrés, arbres syntaxiques issus d'un analyseur à taille limitée, diviser-pour-régner sur des moitiés (la profondeur est logarithmique).
• Convertir lorsque la profondeur est linéaire par rapport à l'entrée : parcourir un arbre avec une pile explicite (en profondeur) ou une file (en largeur) ; remplacer la récursion linéaire par une boucle à accumulateur.
• Là où la récursion subsiste, passer un paramètre de profondeur et échouer proprement à un maximum documenté avant d'atteindre la limite de l'environnement d'exécution, avec une erreur qui nomme la limite.
• Traiter l'augmentation de la limite de récursion comme un pis-aller : elle échange une RecursionError contre un possible débordement de la pile C, et la taille de pile des autres threads se définit séparément de celle du thread principal.
• Mémoïser les fonctions récursives à sous-problèmes chevauchants (voir la programmation dynamique) ; la mémoïsation réduit le travail, pas la profondeur.

Pièges

Convertir en itération change l'ordre de visite sauf si les enfants sont empilés en ordre inverse. La récursion mutuelle cache la profondeur à travers plusieurs fonctions. Les longues chaînes de générateurs délégants (yield from) sont parcourues à chaque reprise ; traiter leur profondeur comme une profondeur de récursion. Les exceptions qui déroulent une pile profonde sont lentes et produisent d'énormes traces. Les __eq__, __repr__ ou sérialiseurs récursifs sur des données cycliques ne se terminent jamais ; suivre les objets déjà visités.

Le plafond de profondeur s'applique aussi à la forme itérative

Remplacer la récursion par une pile explicite ne borne pas la profondeur ; cela déplace la limite de la pile d'appels vers le tas, où l'échec devient une extinction du processus entier par manque de mémoire au lieu d'une RecursionError interceptable. Pour un emboîtement contrôlé par l'entrée (JSON, crochets, arborescences de répertoires), conserver une profondeur maximale documentée dans les deux formes : vérifier le paramètre de profondeur de récursion dans la version récursive, et vérifier la longueur de la pile explicite dans la version itérative, en échouant avec une erreur qui nomme la limite. Les analyseurs intègrent couramment un tel plafond (par exemple serde_json refuse par défaut les documents imbriqués au-delà de 128 niveaux). Un plafond étant en place, le choix entre récursion et itération relève de la clarté et du coût de trame de l'environnement d'exécution, pas de la sécurité.