Vous êtes-vous déjà demandé comment fonctionne réellement la récursivité ? Ce concept qui peut sembler abstrait au premier abord est en réalité l'un des piliers de la programmation. Dans cet article, nous allons décortiquer la récursivité pas à pas, comprendre ce qui se passe vraiment en mémoire, et voir comment l'utiliser efficacement en Python.
Comprendre la récursivité : au-delà de la définition
Qu'est-ce que la récursivité, vraiment ?
La récursivité, c'est une fonction qui s'appelle elle-même pour résoudre un problème. Mais ce n'est pas tout. Le vrai pouvoir de la récursivité vient de sa capacité à décomposer un problème complexe en sous-problèmes identiques mais plus simples.
Prenons une analogie du quotidien. Imaginez que vous devez ranger une pile de 100 livres sur une étagère. Vous pourriez :
-
Approche itérative : prendre chaque livre un par un, 100 fois
-
Approche récursive : prendre le premier livre, puis se dire "maintenant je dois ranger 99 livres", puis "maintenant je dois ranger 98 livres", jusqu'à n'avoir plus aucun livre
La différence peut sembler subtile, mais elle change fondamentalement la façon dont on pense le problème.
L'anatomie d'une fonction récursive
Toute fonction récursive repose sur deux piliers absolument essentiels :
1. Le cas de base : c'est la condition d'arrêt, le moment où on arrête de s'appeler soi-même. Sans cas de base, votre fonction tourne indéfiniment.
2. Le cas récursif : c'est l'appel de la fonction à elle-même, mais avec des paramètres différents qui nous rapprochent du cas de base.
Voyons cela avec l'exemple le plus simple possible.
Premier exemple : compter jusqu'à zéro
def compte_a_rebours(n):
# Cas de base : on s'arrête à 0
if n <= 0:
print("Décollage ! 🚀")
return
# On affiche le nombre actuel
print(n)
# Cas récursif : on s'appelle avec n-1
compte_a_rebours(n - 1)
# Test
compte_a_rebours(5)
Résultat :
5
4
3
2
1
Décollage ! 🚀
Que se passe-t-il vraiment ?
Décomposons l'exécution étape par étape :
-
compte_a_rebours(5)s'exécute, affiche 5, puis appellecompte_a_rebours(4) -
compte_a_rebours(4)s'exécute, affiche 4, puis appellecompte_a_rebours(3) -
compte_a_rebours(3)s'exécute, affiche 3, puis appellecompte_a_rebours(2) -
compte_a_rebours(2)s'exécute, affiche 2, puis appellecompte_a_rebours(1) -
compte_a_rebours(1)s'exécute, affiche 1, puis appellecompte_a_rebours(0) -
compte_a_rebours(0)atteint le cas de base, affiche "Décollage !", et retourne
C'est comme une cascade d'appels qui s'empilent les uns sur les autres.
La pile d'exécution : comprendre ce qui se passe en mémoire
Voici un concept crucial : la pile d'exécution (ou call stack en anglais). C'est la structure de données que Python utilise pour gérer les appels de fonctions.
Visualisons la pile
Prenons un exemple simple avec la factorielle :
def factorielle(n):
print(f"→ Entrée dans factorielle({n})")
if n <= 1:
print(f"← Sortie de factorielle({n}) = 1")
return 1
resultat = n * factorielle(n - 1)
print(f"← Sortie de factorielle({n}) = {resultat}")
return resultat
# Test
print(f"\nRésultat final : {factorielle(4)}\n")
Sortie :
→ Entrée dans factorielle(4)
→ Entrée dans factorielle(3)
→ Entrée dans factorielle(2)
→ Entrée dans factorielle(1)
← Sortie de factorielle(1) = 1
← Sortie de factorielle(2) = 2
← Sortie de factorielle(3) = 6
← Sortie de factorielle(4) = 24
Résultat final : 24
Ce qui se passe vraiment
Phase descendante (empilement) :
factorielle(4) attend le résultat de factorielle(3)
factorielle(3) attend le résultat de factorielle(2)
factorielle(2) attend le résultat de factorielle(1)
factorielle(1) retourne 1 ✓
Phase ascendante (dépilement) :
factorielle(1) retourne 1
factorielle(2) calcule 2 * 1 = 2, retourne 2
factorielle(3) calcule 3 * 2 = 6, retourne 6
factorielle(4) calcule 4 * 6 = 24, retourne 24
Chaque appel de fonction crée un nouveau contexte en mémoire avec ses propres variables locales. C'est comme si chaque appel était une copie indépendante de la fonction.
Application pratique : manipuler des listes de films
Passons maintenant à un exemple concret qui montre toute la puissance de la récursivité. Nous allons travailler avec des données de films.
Problème 1 : Associer des informations
Vous avez deux listes séparées :
-
Une liste de films avec leurs réalisateurs
-
Une liste de budgets
Vous voulez les combiner. Voici comment faire ça de manière récursive :
def associer_listes(liste_films, liste_budgets):
"""
Fusionne deux listes en ajoutant chaque budget au film correspondant.
Exemple :
films = [["Inception", "Nolan"], ["Pulp Fiction", "Tarantino"]]
budgets = [160000000, 8000000]
Résultat : [["Inception", "Nolan", 160000000],
["Pulp Fiction", "Tarantino", 8000000]]
"""
# Cas de base : si une des listes est vide, on arrête
if not liste_films or not liste_budgets:
return []
# On prend le premier film et on lui ajoute le premier budget
premier_element = liste_films[0] + [liste_budgets[0]]
# On traite récursivement le reste des listes
reste = associer_listes(liste_films[1:], liste_budgets[1:])
# On combine le premier élément avec le reste traité
return [premier_element] + reste
Traçons l'exécution
Avec films = [["A"], ["B"], ["C"]] et budgets = [100, 200, 300] :
associer_listes([["A"], ["B"], ["C"]], [100, 200, 300])
│
├─ premier_element = ["A", 100]
├─ appelle associer_listes([["B"], ["C"]], [200, 300])
│ │
│ ├─ premier_element = ["B", 200]
│ ├─ appelle associer_listes([["C"]], [300])
│ │ │
│ │ ├─ premier_element = ["C", 300]
│ │ ├─ appelle associer_listes([], [])
│ │ │ └─ retourne [] (cas de base)
│ │ │
│ │ └─ retourne [["C", 300]]
│ │
│ └─ retourne [["B", 200], ["C", 300]]
│
└─ retourne [["A", 100], ["B", 200], ["C", 300]]
Testez-le !
films = [
["Inception", "Christopher Nolan"],
["Pulp Fiction", "Quentin Tarantino"],
["Le Parrain", "Francis Ford Coppola"],
["Parasite", "Bong Joon-ho"]
]
budgets = [160000000, 8000000, 6000000, 11400000]
resultat = associer_listes(films, budgets)
print("Films avec leurs budgets :")
for film in resultat:
print(f" • {film[0]} de {film[1]} : {film[2]:,}€")
Calculer avec la récursivité : sommes et moyennes
La somme récursive
Comment additionner tous les nombres d'une liste sans utiliser de boucle ?
def somme_recursive(liste):
"""
Calcule la somme des éléments d'une liste.
Logique :
- Liste vide ? Somme = 0
- Sinon ? Somme = premier élément + somme du reste
"""
# Cas de base
if not liste:
return 0
# Cas récursif
premier = liste[0]
reste = liste[1:]
print(f"Calculer : {premier} + somme({reste})")
return premier + somme_recursive(reste)
# Test avec trace
print("\nCalcul détaillé :")
resultat = somme_recursive([10, 20, 30, 40])
print(f"\nRésultat : {resultat}")
Sortie :
Calcul détaillé :
Calculer : 10 + somme([20, 30, 40])
Calculer : 20 + somme([30, 40])
Calculer : 30 + somme([40])
Calculer : 40 + somme([])
Résultat : 100
Compter les éléments
De la même manière, on peut compter les éléments :
def compter_elements(liste):
"""
Compte le nombre d'éléments dans une liste.
Logique :
- Liste vide ? 0 éléments
- Sinon ? 1 (pour l'élément actuel) + nombre d'éléments dans le reste
"""
if not liste:
return 0
return 1 + compter_elements(liste[1:])
# Test
print(compter_elements([10, 20, 30, 40])) # 4
Le budget moyen
Maintenant, combinons nos deux fonctions :
def budget_moyen(liste_budgets):
"""Calcule la moyenne des budgets."""
if not liste_budgets:
return 0
total = somme_recursive(liste_budgets)
nombre = compter_elements(liste_budgets)
return total / nombre
# Test
budgets = [160000000, 8000000, 6000000, 11400000]
moyenne = budget_moyen(budgets)
print(f"Budget moyen : {moyenne:,.0f}€") # 46,350,000€
Filtrer avec la récursivité
Maintenant, utilisons tout ce qu'on a appris pour filtrer les films selon leur budget :
def filtrer_petits_budgets(liste_films, budget_limite):
"""
Garde uniquement les films dont le budget est inférieur à la limite.
Args:
liste_films: Liste de [nom, réalisateur, budget]
budget_limite: Seuil maximum
Returns:
Nouvelle liste filtrée
"""
# Cas de base : liste vide
if not liste_films:
return []
film_actuel = liste_films[0]
budget_actuel = film_actuel[2]
# On filtre récursivement le reste
reste_filtré = filtrer_petits_budgets(liste_films[1:], budget_limite)
# Si le film actuel a un petit budget, on le garde
if budget_actuel < budget_limite:
return [film_actuel] + reste_filtré
else:
return reste_filtré
# Application complète
films = [
["Inception", "Christopher Nolan", 160000000],
["Pulp Fiction", "Quentin Tarantino", 8000000],
["Le Parrain", "Francis Ford Coppola", 6000000],
["Parasite", "Bong Joon-ho", 11400000]
]
moyenne = budget_moyen([f[2] for f in films])
print(f"Budget moyen : {moyenne:,.0f}€\n")
petits_budgets = filtrer_petits_budgets(films, moyenne)
print("Films à petit budget :")
for film in petits_budgets:
print(f" • {film[0]} de {film[1]} : {film[2]:,}€")
Résultat :
Budget moyen : 46,350,000€
Films à petit budget :
• Pulp Fiction de Quentin Tarantino : 8,000,000€
• Le Parrain de Francis Ford Coppola : 6,000,000€
• Parasite de Bong Joon-ho : 11,400,000€
Récursivité vs Itération : le grand débat
Version itérative vs récursive
Comparons les deux approches pour la somme :
# Version itérative (avec boucle)
def somme_iterative(liste):
total = 0
for nombre in liste:
total += nombre
return total
# Version récursive
def somme_recursive(liste):
if not liste:
return 0
return liste[0] + somme_recursive(liste[1:])
Avantages et inconvénients
Récursivité :
-
Code plus élégant et lisible
-
Correspond à la définition mathématique
-
Parfait pour les structures arborescentes
-
Consomme plus de mémoire (pile d'appels)
-
Limite de récursion en Python (~1000 appels)
-
Parfois plus lent
Itération :
-
Plus efficace en mémoire
-
Pas de limite d'itérations
-
Souvent plus rapide
-
Code parfois moins intuitif
-
Difficile pour structures complexes
Quand utiliser la récursivité ?
Utilisez la récursivité pour :
-
Parcourir des arbres (fichiers, DOM, JSON)
-
Algorithmes naturellement récursifs (quicksort, merge sort)
-
Problèmes diviser-pour-régner
-
Backtracking (sudoku, échecs)
Privilégiez l'itération pour :
-
Listes très longues
-
Calculs simples (sommes, moyennes)
-
Performance critique
-
Traitements linéaires
Exemple avancé : aplatir une liste imbriquée
Voici un cas où la récursivité excelle vraiment :
def aplatir(liste):
"""
Aplatit une liste de n'importe quelle profondeur.
Exemple : [[1, [2, 3]], [[4], 5]] → [1, 2, 3, 4, 5]
"""
# Liste vide
if not liste:
return []
premier = liste[0]
reste = liste[1:]
# Si le premier élément est lui-même une liste, on l'aplatit
if isinstance(premier, list):
return aplatir(premier) + aplatir(reste)
else:
# Sinon, on le garde tel quel
return [premier] + aplatir(reste)
# Tests
print(aplatir([1, 2, 3])) # [1, 2, 3]
print(aplatir([[1, 2], [3, 4]])) # [1, 2, 3, 4]
print(aplatir([[1, [2, 3]], [[4], 5]])) # [1, 2, 3, 4, 5]
print(aplatir([[[[[1]]]], 2])) # [1, 2]
Traçons l'exécution
Pour [[1, 2], 3] :
aplatir([[1, 2], 3])
├─ premier = [1, 2] (c'est une liste)
├─ on appelle aplatir([1, 2])
│ ├─ premier = 1 (pas une liste)
│ └─ retourne [1] + aplatir([2])
│ └─ retourne [1, 2]
│
├─ on appelle aplatir([3])
│ └─ retourne [3]
│
└─ retourne [1, 2] + [3] = [1, 2, 3]
Optimisation : la récursivité terminale
Un problème avec la récursivité classique est qu'elle conserve tous les contextes en mémoire. La récursivité terminale résout ce problème en utilisant un accumulateur :
# Version classique (non optimisée)
def somme_classique(liste):
if not liste:
return 0
return liste[0] + somme_classique(liste[1:])
# Version avec récursivité terminale
def somme_terminale(liste, accumulateur=0):
"""
Le dernier appel est directement la fonction récursive,
sans calcul supplémentaire après.
"""
if not liste:
return accumulateur
# On accumule au fur et à mesure
return somme_terminale(liste[1:], accumulateur + liste[0])
# Test
print(somme_terminale([1, 2, 3, 4, 5])) # 15
La différence cruciale : dans la version terminale, il n'y a aucun calcul après l'appel récursif. Le résultat de l'appel récursif EST le résultat de la fonction.
Erreurs courantes à éviter
1. Oublier le cas de base
# ❌ ERREUR : RecursionError
def mauvaise_fonction(n):
return n + mauvaise_fonction(n - 1) # Pas de cas de base !
2. Cas de base jamais atteint
# ❌ ERREUR : Le cas de base n'est jamais atteint
def mauvaise_factorielle(n):
if n == 1: # Mais que se passe-t-il si n = 0 ?
return 1
return n * mauvaise_factorielle(n - 1)
3. Ne pas se rapprocher du cas de base
# ❌ ERREUR : On ne se rapproche pas du cas de base
def mauvais_compte(n):
if n == 0:
return
print(n)
mauvais_compte(n) # On devrait faire n-1 !
Exercices pratiques pour progresser
Essayez d'implémenter ces fonctions de manière récursive :
Exercice 1 : Inverser une liste
def inverser(liste):
"""[1, 2, 3] → [3, 2, 1]"""
# À vous de coder !
pass
Exercice 2 : Trouver le maximum
def maximum(liste):
"""Trouve le plus grand élément"""
# À vous de coder !
pass
Exercice 3 : Palindrome
def est_palindrome(texte):
"""Vérifie si un texte est un palindrome"""
# À vous de coder !
pass
Exercice 4 : Suite de Fibonacci
def fibonacci(n):
"""Calcule le n-ième terme de Fibonacci"""
# À vous de coder !
pass
Solutions
Cliquez pour voir les solutions
# Solution 1 : Inverser
def inverser(liste):
if not liste:
return []
return inverser(liste[1:]) + [liste[0]]
# Solution 2 : Maximum
def maximum(liste):
if len(liste) == 1:
return liste[0]
max_reste = maximum(liste[1:])
return liste[0] if liste[0] > max_reste else max_reste
# Solution 3 : Palindrome
def est_palindrome(texte):
texte = texte.lower().replace(" ", "")
if len(texte) <= 1:
return True
if texte[0] != texte[-1]:
return False
return est_palindrome(texte[1:-1])
# Solution 4 : Fibonacci
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2)
Conclusion
La récursivité est bien plus qu'une technique de programmation : c'est une façon de penser les problèmes. En décomposant un problème complexe en versions plus simples de lui-même, on arrive souvent à des solutions élégantes et puissantes.
Les points clés à retenir :
-
Toujours définir un cas de base clair et atteignable
-
Chaque appel récursif doit se rapprocher du cas de base
-
Comprendre la pile d'exécution aide à déboguer
-
Choisir entre récursivité et itération selon le contexte
-
Utiliser la récursivité terminale pour optimiser
La maîtrise de la récursivité demande de la pratique. Commencez par des exemples simples, tracez l'exécution sur papier, et progressivement vous développerez cette intuition récursive qui transforme des problèmes complexes en solutions élégantes.
Bon code ! 🚀
Laisser un commentaire