Les fonctions récursives en Python

La condition d'arrêt : la règle numéro un

Toute fonction récursive doit inclure une condition d'arrêt — aussi appelée cas de base. Sans elle, la fonction s'appelle indéfiniment jusqu'à ce que Python lève une erreur (RecursionError: maximum recursion depth exceeded). La structure minimale ressemble à ceci :

def fn():
    if condition:
        return  # cas de base : on arrête les appels
    fn()        # appel récursif tant que la condition n'est pas atteinte

La récursion est couramment utilisée pour résoudre des problèmes qui se décomposent naturellement en sous-problèmes identiques : parcours d'arbres, recherche binaire, calculs mathématiques cumulatifs.

Exemple 1 : un compte à rebours récursif

On veut afficher les nombres de 3 à 0 dans l'ordre décroissant. Sans récursion, il faudrait quatre appels manuels. Avec une fonction récursive, la fonction se rappelle elle-même en décrémentant le nombre à chaque fois.

Voici d'abord la version naïve — sans condition d'arrêt — pour comprendre pourquoi elle pose problème :

def compte_a_rebours(debut):
    print(debut)
    compte_a_rebours(debut - 1)  # pas de condition d'arrêt → boucle infinie
compte_a_rebours(3)

Ce code tourne indéfiniment jusqu'à l'erreur. On corrige en ajoutant la condition d'arrêt : on ne rappelle la fonction que si le prochain nombre est supérieur ou égal à zéro.

def compte_a_rebours(debut):
    """Compte à rebours depuis un nombre jusqu'à 0."""
    print(debut)
    if debut - 1 >= 0:
        compte_a_rebours(debut - 1)  # appel récursif seulement si le suivant est >= 0
compte_a_rebours(3)
# Affiche : 3, 2, 1, 0

Exemple 2 : somme d'une séquence

Calculons la somme des entiers de 1 à n. La version itérative avec for fonctionne, mais la version récursive est plus courte et reflète directement la définition mathématique : somme(n) = n + somme(n-1), avec somme(0) = 0 comme cas de base.

# Version itérative avec for
def somme(n):
    total = 0
    for index in range(n + 1):
        total += index
    return total
print(somme(50))  # 1275

La version récursive traduit la même logique sans boucle :

# Version récursive : somme(n) = n + somme(n-1)
def somme(n):
    if n > 0:
        return n + somme(n - 1)  # appel récursif avec n-1
    return 0  # cas de base : somme(0) = 0
print(somme(50))  # 1275

On peut encore condenser avec l'opérateur ternaire, si la lisibilité le permet :

# Version condensée avec opérateur ternaire
def somme(n):
    return n + somme(n - 1) if n > 0 else 0
print(somme(50))  # 1275

Les trois versions produisent le même résultat. La récursive est plus proche du raisonnement mathématique ; l'itérative est souvent plus lisible pour un débutant.

Par carabde | Mis à jour le 24 avril 2026