Les fonctions récursives en langage Python#
Une fonction est dite récursive lorsqu'elle s'appelle elle-même au cours de sa propre exécution pour résoudre une sous-partie plus simple du problème initial. Ce paradigme, omniprésent en mathématiques et dans les algorithmes de type « Diviser pour régner » (Divide and Conquer), permet d'exprimer des solutions remarquablement concises pour parcourir des structures arborescentes ou traiter des suites récurrentes.
1. Les deux piliers de la récursivité#
Pour qu'une fonction récursive soit correcte et ne boucle pas indéfiniment, elle doit impérativement respecter deux conditions :
flowchart TD
A[Appel de la fonction f\(n\)] --> B{Cas de base atteint ?}
B -->|Oui : Condition d'arrêt| C[Retourne une valeur directe sans récursion]
B -->|Non : Pas récursif| D[Appel récursif avec un problème réduit f\(n-1\)]
D --> A
- Le cas de base (ou condition d'arrêt) : une condition d'arrêt explicite qui renvoie un résultat direct sans effectuer de nouvel appel récursif.
- Le pas récursif (ou progression) : l'appel de la fonction sur un sous-problème plus petit, garantissant que l'on se rapproche inévitablement du cas de base.
2. Exemple classique : Le calcul de la factorielle#
Par définition mathématique, la factorielle d'un entier \(n \ge 0\) (notée \(n!\)) est définie par : $\(0! = 1 \qquad \text{et} \qquad n! = n \times (n - 1)! \quad (\forall n \ge 1)\)$
def factorielle(n: int) -> int:
"""Calcule la factorielle de n de manière récursive."""
if n < 0:
raise ValueError("La factorielle n'est pas definie pour les nombres negatifs.")
# 1. Cas de base
if n == 0 or n == 1:
return 1
# 2. Pas récursif
return n * factorielle(n - 1)
print("5! =", factorielle(5)) # 5 * 4 * 3 * 2 * 1 = 120
Que se passe-t-il dans la pile d'appels (Call Stack) ?#
Lors de l'appel factorielle(3), l'interpréteur Python empile les contextes d'exécution successifs :
[ Empilement ]
factorielle(3) -> attend 3 * factorielle(2)
factorielle(2) -> attend 2 * factorielle(1)
factorielle(1) -> Cas de base atteint ! Retourne 1
[ Dépilement et calculs ]
factorielle(1) = 1
factorielle(2) = 2 * 1 = 2
factorielle(3) = 3 * 2 = 6
3. La limite de récursion en Python : RecursionError#
Chaque appel de fonction consomme un cadre (frame) dans la mémoire de la pile d'appels. Pour éviter qu'un bogue récursif n'épuise la mémoire vive de votre machine (Stack Overflow), Python impose un plafond de sécurité strict :
import sys
# Consulter la profondeur maximale autorisée (généralement 1000)
print("Limite de recursion par defaut :", sys.getrecursionlimit())
# Si le cas de base n'est jamais atteint :
def boucle_infinie(n):
return boucle_infinie(n + 1)
# boucle_infinie(1) -> Lève RecursionError: maximum recursion depth exceeded
4. La suite de Fibonacci et le piège de la complexité exponentielle#
La suite de Fibonacci est définie par \(F_0 = 0\), \(F_1 = 1\) et \(F_n = F_{n-1} + F_{n-2}\).
L'implémentation récursive naïve (Très lente : \(\mathcal{O}(2^n)\))#
def fibonacci_naif(n: int) -> int:
if n <= 0:
return 0
if n == 1:
return 1
return fibonacci_naif(n - 1) + fibonacci_naif(n - 2)
# fibonacci_naif(35) prend plusieurs secondes car chaque appel se dédouble !
L'optimisation par mémoïsation : @functools.lru_cache#
Le décorateur natif lru_cache intercepte les appels de la fonction et met en cache (memoize) les résultats déjà calculés. La complexité chute de \(\mathcal{O}(2^n)\) à \(\mathcal{O}(n)\) !
from functools import lru_cache
import time
@lru_cache(maxsize=None)
def fibonacci_optimise(n: int) -> int:
if n <= 0:
return 0
if n == 1:
return 1
return fibonacci_optimise(n - 1) + fibonacci_optimise(n - 2)
debut = time.perf_counter()
res = fibonacci_optimise(100)
fin = time.perf_counter()
print(f"F(100) = {res}")
print(f"Calcule en {(fin - debut) * 1000:.4f} millisecondes !")
5. Autre cas d'école : Vérification récursive d'un palindrome#
Un mot est un palindrome s'il se lit de la même façon de gauche à droite et de droite à gauche (ex: radar, kayak).
def est_palindrome_recursif(mot: str) -> bool:
"""Vérifie récursivement si une chaîne est un palindrome."""
# Nettoyage
chaine = mot.lower().replace(" ", "")
# Cas de base 1 : un mot vide ou d'une seule lettre est un palindrome
if len(chaine) <= 1:
return True
# Cas de base 2 : si les extrémités diffèrent, ce n'est pas un palindrome
if chaine[0] != chaine[-1]:
return False
# Pas récursif : tester le sous-mot sans les deux extrémités
return est_palindrome_recursif(chaine[1:-1])
print("kayak :", est_palindrome_recursif("kayak")) # True
print("radar :", est_palindrome_recursif("radar")) # True
print("python :", est_palindrome_recursif("python")) # False
6. Récursif vs Itératif : Quand utiliser quoi ?#
| Critère | Approche Récursive | Approche Itérative (for / while) |
|---|---|---|
| Lisibilité | Très élégante pour les problèmes divisibles (arbres, graphes) | Souvent plus verbeuse pour les structures complexes |
| Consommation mémoire | Plus élevée (chaque appel occupe un cadre de pile) | Minimale (\(\mathcal{O}(1)\) mémoire auxiliaire) |
| Vitesse d'exécution | Légèrement plus lente en Python (surcoût d'appel de fonction) | Généralement plus rapide |
| Risque de crash | Risque de RecursionError sur grands volumes (\(N > 1000\)) |
Aucun risque de dépassement de pile |
7. Défi d'application#
Écrivez une fonction récursive somme_chiffres(n: int) -> int qui prend en entrée un entier positif quelconque (ex: 12345) et calcule la somme de ses chiffres individuels (\(1 + 2 + 3 + 4 + 5 = 15\)) en utilisant les opérateurs de division entière // 10 et de modulo % 10.
Commentaires