Maîtriser la récursivité en Python : Comment les fonctions s'appellent elles-mêmes

Maîtriser la récursivité en Python

Découvrez comment les fonctions Python peuvent s'appeler elles-mêmes, la mécanique de la récursivité et les bonnes pratiques pour écrire du code récursif sûr et efficace.

Qu'est-ce que la récursivité ?

La récursivité est la technique de définir un problème en termes d'une instance plus petite du même problème.

Une illustration classique implique deux miroirs parallèles se faisant face ; chaque image est une réflexion récursive de l'autre.

---

Fonction récursive en Python

En Python, une fonction peut invoquer d'autres fonctions, et elle peut même s'invoquer elle-même. De tels constructs sont appelés fonctions récursives.

L'image ci-dessous démontre la pile d'appels pour une fonction récursive simple nommée recurse :

Voici un exemple classique : une implémentation récursive de la fonction factorielle, qui retourne le produit de tous les entiers positifs jusqu'à x.

Exemple de fonction récursive

def factorial(x):
    """Calcule récursivement le factoriel d'un entier positif."""
    if x == 1:
        return 1
    return x * factorial(x - 1)
num = 3
print("Le factoriel de", num, "est", factorial(num))

Sortie

Le factoriel de 3 est 6

Ici, factorial() est une fonction récursive car elle s'appelle elle-même jusqu'à ce que le cas de base x == 1 soit atteint.

Lorsqu'elle est invoquée avec un entier positif, la fonction s'appelle répétitivement avec une valeur décrémentée :

factorial(3) # 1er appel avec 3
3 * factorial(2) # 2ème appel avec 2
3 * 2 * factorial(1) # 3ème appel avec 1
3 * 2 * 1 # retour du 3ème appel
3 * 2 # retour du 2ème appel
6 # retour du 1er appel

Voici une représentation visuelle de ce processus étape par étape :

La récursivité se termine quand la valeur d'entrée atteint la condition de base (dans ce cas, x == 1). Toute fonction récursive doit inclure un tel critère d'arrêt ; sinon, elle continuerait indéfiniment et épuiserait éventuellement la pile d'appels.

Python impose une profondeur de récursion maximale (par défaut 1000) pour empêcher la récursion infinie de faire planter l'interpréteur. Dépasser cette limite lève une RecursionError :

def recursor():
    recursor()
recursor()

Sortie

Traceback (most recent call last):
File "<string>", line 3, in <module>
File "<string>", line 2, in a
File "<string>", line 2, in a
File "<string>", line 2, in a
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Vous pouvez ajuster la limite de récursion programmatiquement en utilisant sys.setrecursionlimit(), mais faites-le avec prudence pour éviter le débordement de pile.

---

Avantages de la récursivité

1. Les solutions récursives sont souvent plus concises et plus faciles à lire, surtout pour les problèmes naturellement exprimés en termes récursifs.
2. Elles permettent une décomposition élégante de tâches complexes en sous-problèmes plus simples.
3. La génération de séquences (ex. Fibonacci, permutations) est simple avec la récursivité comparée aux boucles imbriquées.

---

Inconvénients de la récursivité

1. La logique récursive peut être plus difficile à suivre et à raisonner pour les débutants.
2. Chaque appel récursif consomme de l'espace de pile ; les récursions profondes peuvent être gourmandes en mémoire et plus lentes que les alternatives itératives.
3. Le débogage de la récursivité peut être difficile en raison de la pile d'appels en couches.

En pratique, choisissez la récursivité quand elle mène à un code plus clair et plus maintenable et quand la taille d'entrée est modérée. Pour des entrées très grandes, les approches itératives ou les optimisations de récursion terminale (quand supportées) peuvent être préférables.