La récursion en Python

La récursion est une technique où une fonction s'appelle elle-même pour résoudre un problème en le décomposant en sous-problèmes plus petits et identiques. Chaque appel traite une version plus simple du problème d'origine jusqu'à atteindre un cas trivial — le cas de base — qui peut être résolu directement.

Ce chapitre couvre :

• Comment fonctionne la récursion et à quoi ressemble la pile d'appels
• Le cas de base et le cas récursif
• Les problèmes récursifs classiques : factorielle, Fibonacci, puissance, aplatissement
• Récursion vs itération — quand choisir l'une ou l'autre
• La limite de récursion de Python et comment la contourner
• La mémoïsation avec functools.lru_cache

Comment fonctionne la récursion

Lorsqu'une fonction s'appelle elle-même, Python empile un nouveau cadre de pile sur la pile d'appels pour chaque appel. Chaque cadre conserve ses propres variables locales. Lorsque le cas de base est atteint, les cadres commencent à retourner dans l'ordre inverse — dernier entré, premier sorti — jusqu'à ce que l'appel d'origine reçoive sa réponse finale.

Une fonction récursive valide comporte toujours deux parties :

Sans cas de base (ou avec un cas de base jamais atteint), la fonction s'appelle indéfiniment et Python lève une RecursionError.

Un exemple simple : le compte à rebours

La fonction suivante effectue un compte à rebours de n jusqu'à zéro, puis affiche "Go!". Elle est facile à suivre car chaque appel réduit n de un jusqu'à ce que n <= 0.

def countdown(n):
    if n <= 0:         # base case
        print("Go!")
        return
    print(n)
    countdown(n - 1)   # recursive case

countdown(5)

Sortie :

5
4
3
2
1
Go!

Trace de la pile d'appels :

1. countdown(5) affiche 5, appelle countdown(4)
2. countdown(4) affiche 4, appelle countdown(3)
3. … et ainsi de suite …
4. countdown(0) affiche "Go!" et retourne — le déroulement commence

Factorielle

La factorielle de n (notée n!) est le produit de tous les entiers positifs jusqu'à n. Elle est définie récursivement comme suit :

• 0! = 1 (cas de base)
• n! = n × (n − 1)! (cas récursif)

def factorial(n):
    if n == 0 or n == 1:   # base case
        return 1
    return n * factorial(n - 1)

print(factorial(5))    # 120
print(factorial(0))    # 1
print(factorial(10))   # 3628800

factorial(5) se développe ainsi avant qu'une valeur ne soit retournée :

factorial(5)
  5 * factorial(4)
        4 * factorial(3)
              3 * factorial(2)
                    2 * factorial(1)
                          1          ← base case

Puis les multiplications s'effectuent au retour : 1 → 2 → 6 → 24 → 120.

Suite de Fibonacci

La suite de Fibonacci est définie ainsi : chaque nombre est la somme des deux précédents — 0, 1, 1, 2, 3, 5, 8, 13, …

def fibonacci(n):
    if n <= 0:   # base case
        return 0
    if n == 1:   # base case
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

for i in range(8):
    print(fibonacci(i), end=" ")
# Output: 0 1 1 2 3 5 8 13

Cette approche est correcte mais lente pour de grandes valeurs de n — fibonacci(40) effectue des millions d'appels redondants. Consultez Mémoïsation ci-dessous pour la solution.

Somme d'une liste

La récursion s'applique naturellement aux listes : traiter le premier élément, puis récurer sur le reste.

def sum_list(lst):
    if not lst:              # base case — empty list
        return 0
    return lst[0] + sum_list(lst[1:])

print(sum_list([1, 2, 3, 4, 5]))   # 15
print(sum_list([]))                 # 0

lst[1:] crée une nouvelle liste sans le premier élément, réduisant le problème d'un élément à chaque fois.

Élever un nombre à une puissance

def power(base, exp):
    if exp == 0:          # base case: anything to the power 0 is 1
        return 1
    return base * power(base, exp - 1)

print(power(2, 10))   # 1024
print(power(3, 4))    # 81
print(power(5, 0))    # 1

Aplatissement d'une liste imbriquée

Certains problèmes sont intrinsèquement récursifs — ils ont la même structure à chaque niveau. Aplatir une liste imbriquée de profondeur arbitraire en est un exemple.

def flatten(lst):
    result = []
    for item in lst:
        if isinstance(item, list):
            result.extend(flatten(item))   # recurse into sublists
        else:
            result.append(item)
    return result

print(flatten([1, [2, 3], [4, [5, 6]], 7]))
# [1, 2, 3, 4, 5, 6, 7]

C'est difficile à écrire proprement avec la seule itération car la profondeur d'imbrication est inconnue.

Récursion vs itération

La plupart des algorithmes récursifs peuvent être réécrits sous forme de boucles itératives, et vice versa.

Factorielle itérative

def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

print(factorial_iterative(5))   # 120

Règle pratique : choisissez la récursion lorsque le problème se décompose naturellement en sous-problèmes identiques plus petits et que la profondeur est modeste. Choisissez l'itération quand vous avez besoin de hautes performances ou que la profondeur peut être grande.

La limite de récursion de Python

Python limite la pile d'appels à 1 000 cadres par défaut pour éviter qu'un dépassement de pile ne fasse planter le processus.

import sys
print(sys.getrecursionlimit())   # 1000

Si votre fonction dépasse cette limite, vous verrez :

RecursionError: maximum recursion depth exceeded

Vous pouvez augmenter la limite avec sys.setrecursionlimit(n), mais avec prudence — une pile très profonde peut épuiser la mémoire système. Pour une récursion réellement profonde, réécrivez l'algorithme de façon itérative ou utilisez les générateurs Python pour simuler manuellement une pile.

Mémoïsation

La récursion naïve de Fibonacci est exponentiellement lente car elle résout les mêmes sous-problèmes à répétition. La mémoïsation met en cache le résultat de chaque appel unique afin qu'il ne soit calculé qu'une seule fois.

Cache manuel avec un dictionnaire

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 0:
        return 0
    if n == 1:
        return 1
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

print(fibonacci(10))   # 55
print(fibonacci(30))   # 832040

Utiliser functools.lru_cache

La bibliothèque standard fournit un décorateur qui gère la mise en cache automatiquement :

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(10))   # 55
print(fibonacci(50))   # 12586269025

@lru_cache transforme un algorithme autrement exponentiel en temps linéaire sans aucun code supplémentaire dans le corps de la fonction. C'est l'approche idiomatique de Python pour mémoïser des fonctions récursives pures.

Recherche binaire (récursive)

La recherche binaire est un algorithme classique de type diviser pour régner : comparer la cible à l'élément du milieu, puis récurer sur la moitié gauche ou droite.

def binary_search(lst, target, low=0, high=None):
    if high is None:
        high = len(lst) - 1
    if low > high:        # base case: search space exhausted
        return -1
    mid = (low + high) // 2
    if lst[mid] == target:
        return mid
    elif lst[mid] < target:
        return binary_search(lst, target, mid + 1, high)
    else:
        return binary_search(lst, target, low, mid - 1)

nums = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(nums, 7))    # 3
print(binary_search(nums, 1))    # 0
print(binary_search(nums, 15))   # 7
print(binary_search(nums, 4))    # -1  (not found)

Pièges courants

Cas de base manquant

# This will raise RecursionError
def broken(n):
    return n * broken(n - 1)   # no base case!

Posez-vous toujours la question : « Quelle est l'entrée la plus simple que cette fonction doit traiter sans s'appeler elle-même ? »

Récursion infinie due à un mauvais cas de base

# factorial of a negative number loops forever
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)   # n goes -1, -2, -3 ...

# Fix: guard at the top
def factorial(n):
    if n < 0:
        raise ValueError("n must be non-negative")
    if n == 0:
        return 1
    return n * factorial(n - 1)

Argument par défaut mutable comme cache

Utiliser memo={} comme paramètre par défaut est pratique, mais partage l'état entre tous les appels de premier niveau. Pour du code en production, passez le cache explicitement ou utilisez @lru_cache.

Quand utiliser la récursion

La récursion convient naturellement pour :

• Le parcours d'arbres et de graphes — listings de répertoires, parcours du DOM, arbres de décision
• Les algorithmes diviser pour régner — tri fusion, quicksort, recherche binaire
• Les définitions mathématiques — factorielle, Fibonacci, combinatoires
• Le backtracking — résolution de labyrinthes, Sudoku, génération de permutations
• Les structures de données imbriquées — analyse JSON/XML, aplatissement de listes imbriquées

Pour de simples boucles séquentielles ou de grandes profondeurs, préférez les boucles for ou les boucles while.

Chapitres associés

• Fonctions Python — les blocs de base sur lesquels repose la récursion
• Portée Python — comprendre comment les variables locales fonctionnent dans chaque cadre
• Boucles while Python — l'alternative itérative
• Générateurs Python — alternatives efficaces en mémoire pour les séquences
• Itérateurs Python — le protocole d'itération sous-jacent au modèle de boucle de Python
• Python Try Except — gérer RecursionError de façon élégante

Pratique