Récursivité

Vue d'ensemble

Une fonction récursive est une fonction qui, pour résoudre un problème, s'appelle elle-même sur un cas plus petit. C'est une façon de penser aussi fondamentale que la boucle, et un grand classique des concours : beaucoup d'algorithmes (dichotomie, tri, parcours d'arbres) s'expriment naturellement de façon récursive. Le secret tient en deux ingrédients : un cas de base qui arrête la descente, et un cas récursif qui se rapproche de ce cas de base. Cette fiche te fait écrire le code, le décrypter ligne par ligne, suivre la pile d'appels pas à pas, puis comprendre pourquoi ça termine — et pourquoi ça peut coûter très cher.

Au programme (tronc commun, 1^re année — BO 2021) — Notion de fonction récursive ; cas de base et cas récursif ; terminaison d'une récursion ; lien entre récursivité et méthode « diviser pour régner » ; premiers exemples (factorielle, suites, parcours de listes).

Prérequis

Écrire et appeler une fonction Python avec def et return
Instruction conditionnelle if / else
Manipuler une liste : indexation t[0], tranche t[1:], liste vide []

🎯 Accompagnement Majorant

La récursivité te donne le vertige — tu ne « vois » pas comment un appel peut en attendre un autre ? C'est le passage obligé qui bloque presque tout le monde en Sup. Nos mentors alumni X · Centrale · Mines déroulent la pile d'appels avec toi, sur tes propres exercices, jusqu'à ce que le raisonnement récursif devienne un réflexe.

Trouver un mentor →

1. Définition : cas de base et cas récursif

Définition 1.1 — Fonction récursive

Une fonction est récursive lorsqu'elle s'appelle elle-même dans son propre corps. Pour ne pas tourner indéfiniment, elle doit toujours comporter :

un cas de base : une situation simple où la réponse est connue directement, sans appel récursif — c'est la condition d'arrêt ;
un cas récursif : la fonction se rappelle sur une donnée plus proche du cas de base (par exemple un entier plus petit, une liste plus courte).

📝 L'image mentale. Une fonction récursive délègue : « je ne sais pas résoudre le gros problème, mais je sais le ramener à un problème un peu plus petit, que je confie à une copie de moi-même ». Le cas de base est le plus petit problème, celui que l'on sait résoudre sans déléguer.

⚠ Pas de cas de base = catastrophe. Une fonction récursive sans cas de base (ou dont le cas de base n'est jamais atteint) s'appelle sans fin. Python empile les appels jusqu'à saturer la mémoire réservée, puis lève une RecursionError. Un cas de base est donc obligatoire, et il faut vérifier qu'on s'en rapproche vraiment.

2. Exemple canonique : la factorielle

La factorielle $n! = 1 \times 2 \times \dots \times n$ se définit récursivement par $0! = 1$ (cas de base) et $n! = n \times (n - 1)!$ (cas récursif). Cette définition mathématique se traduit presque mot pour mot en Python.

def factorielle(n):
    if n == 0:
        return 1              # cas de base
    return n * factorielle(n - 1)   # cas recursif

print(factorielle(3))   # affiche 6

🔍 Décryptage ligne par ligne

if n == 0:
    return 1

Le cas de base. Quand n vaut 0, la réponse est connue :

0! = 1

. On renvoie 1 sans se rappeler. C'est ce qui arrête la descente.

return n * factorielle(n - 1)Le cas récursif. Pour calculer

n!

, on multiplie n par le résultat de factorielle(n - 1). On délègue le calcul de

(n - 1)!

à un nouvel appel, sur un argument plus petit : on se rapproche du cas de base.

n - 1Le rapprochement. C'est la clé de la terminaison : chaque appel reçoit un n diminué de 1. En partant d'un entier positif, on finit forcément par atteindre 0.

Pour voir la récursivité à l'œuvre, il faut suivre la pile d'appels : les appels s'empilent pendant la descente (chacun met le suivant « en attente »), puis se dépilent pendant la remontée (chacun reçoit le résultat de celui qu'il attendait).

Pile d'appels — factorielle(3)
Étape	Phase	Appel en cours	Ce qui se passe	Renvoie
1	descente	factorielle(3)	3 ≠ 0 → en attente de 3 × factorielle(2)	—
2	descente	factorielle(2)	2 ≠ 0 → en attente de 2 × factorielle(1)	—
3	descente	factorielle(1)	1 ≠ 0 → en attente de 1 × factorielle(0)	—
4	base	factorielle(0)	cas de base : n == 0	1
5	remontée	factorielle(1)	calcule 1 × 1	1
6	remontée	factorielle(2)	calcule 2 × 1	2
7	remontée	factorielle(3)	calcule 3 × 2	6 ✓

💡 À retenir. Rien n'est calculé « au fond » : à l'étape 4 on connaît seulement factorielle(0) = 1. Les multiplications ne se font qu'à la remontée, quand chaque appel récupère le résultat de son sous-appel. C'est pour ça qu'un dessin de la pile (descente puis remontée) est le meilleur outil pour comprendre — ou débugger — une fonction récursive.

3. Pourquoi ça termine (et quand ça boucle)

Une récursion est correcte seulement si elle s'arrête. L'argument doit décroître strictement à chaque appel et finir par atteindre le cas de base.

Théorème 3.1 — Terminaison d'une récursion sur un entier ★ À savoir démontrer

Soit une fonction récursive dont le cas de base est n == 0 et dont chaque appel récursif se fait sur n - 1, avec n entier positif au départ. Alors le nombre d'appels imbriqués est fini (au plus $n + 1$ ) : la fonction termine.

Démonstration

À chaque appel, on associe la valeur entière $n$ de son argument. Cette quantité, appelée variant, est un entier positif ( $n \geq 0$ , sinon on aurait dépassé le cas de base). À chaque appel récursif, on passe de $n$ à $n - 1$ : le variant décroît strictement d'exactement 1.

Or une suite d'entiers positifs strictement décroissante ne peut pas être infinie : elle ne peut pas descendre en dessous de 0. Partant de $n$ , on atteint donc $0$ après exactement $n$ appels récursifs, et l'appel n == 0 renvoie sans se rappeler. La récursion comporte au plus $n + 1$ appels et s'arrête. $■$

⚠ Le cas de base jamais atteint. Si l'argument ne décroît pas vers le cas de base, la récursion est infinie. Exemple typique d'une factorielle mal écrite : appeler factorielle(n + 1) au lieu de n - 1, ou tester n == 0 alors qu'on part d'un n négatif. Dans les deux cas, Python empile les appels jusqu'à lever :

def factorielle_ratee(n):
    if n == 0:
        return 1
    return n * factorielle_ratee(n + 1)   # BUG : n augmente, n == 0 jamais atteint

factorielle_ratee(3)
# RecursionError: maximum recursion depth exceeded

📝 Le réflexe de vérification. Devant toute fonction récursive, pose-toi deux questions : (1) Y a-t-il un cas de base ? (2) Chaque appel se rapproche-t-il de ce cas de base ? Si tu réponds « oui » aux deux, la fonction termine. Si tu hésites sur la seconde, cherche le variant : la quantité entière positive qui décroît.

4. Un deuxième exemple : la somme d'une liste

Même schéma sur une liste. La somme d'une liste vide vaut 0 (cas de base) ; sinon, c'est le premier élément plus la somme du reste de la liste (cas récursif). Le « reste » t[1:] est une liste plus courte : on se rapproche de la liste vide.

def somme(t):
    if t == []:
        return 0                 # cas de base : liste vide
    return t[0] + somme(t[1:])   # cas recursif : premier + somme du reste

print(somme([4, 7, 2, 5]))   # affiche 18

🔍 Décryptage ligne par ligne

if t == []:
    return 0

Le cas de base. Une liste vide n'a rien à additionner : sa somme vaut 0. On renvoie 0 sans se rappeler.

t[0]Le premier élément. C'est la part qu'on traite « tout de suite » à cet appel.

somme(t[1:])Le reste, délégué. t[1:] est la liste privée de sa première case — plus courte d'un élément. On confie sa somme à un nouvel appel : on se rapproche de la liste vide.

t[0] + somme(t[1:])On recolle. À la remontée, chaque appel ajoute son premier élément à la somme du reste que l'appel suivant lui a renvoyée. En déroulant : somme([5]) renvoie 5, somme([2, 5]) renvoie 7, somme([7, 2, 5]) renvoie 14, et somme([4, 7, 2, 5]) renvoie 4 + 14 = 18.

📐 Méthode — écrire une fonction récursive.

Identifie le cas de base : quelle est la plus petite entrée dont tu connais la réponse sans calcul ? (entier 0, liste vide…)
Écris le cas récursif : exprime le résultat sur l'entrée courante en fonction du résultat sur une entrée plus petite.
Vérifie le rapprochement : assure-toi que l'appel récursif se fait bien sur une entrée strictement plus proche du cas de base.
Teste sur une petite entrée et déroule la pile d'appels si tu doutes.

5. Le piège du coût : Fibonacci récursif naïf

La récursivité est élégante, mais peut être catastrophiquement lente si un même calcul est refait plusieurs fois. Le cas d'école est la suite de Fibonacci $F_{0} = 0, F_{1} = 1, F_{n} = F_{n - 1} + F_{n - 2}$ , qui se code en deux appels récursifs.

def fib(n):
    if n <= 1:
        return n                 # cas de base : fib(0)=0, fib(1)=1
    return fib(n - 1) + fib(n - 2)

print(fib(10))   # affiche 55

🔍 Décryptage ligne par ligne

if n <= 1:
    return n

Deux cas de base d'un coup. Pour n = 0 on renvoie 0, pour n = 1 on renvoie 1. Le test n <= 1 couvre les deux.

return fib(n - 1) + fib(n - 2)Deux appels récursifs. Contrairement à la factorielle (un seul appel), chaque appel en déclenche deux. C'est là que le coût explose.

⚠ Le même calcul, encore et encore. Pour évaluer fib(5), l'appel fib(3) est recalculé 2 fois, fib(2) 3 fois, et ainsi de suite. Le nombre total d'appels pour fib(n) croît de façon exponentielle : environ

O (φ^{n})

avec

φ = \frac{1 + 5}{2} \approx 1, 618

. Concrètement, fib(5) déclenche 15 appels, fib(10) en déclenche 177, et fib(50) serait hors de portée. Un même sous-problème est résolu des milliers de fois.

📝 La parade (hors programme de 1^re année). On corrige ce gaspillage en mémorisant les résultats déjà calculés (mémoïsation) ou en passant à une version itérative — coût alors linéaire en

n

. Retiens surtout, pour l'instant, que récursif n'est pas synonyme d'efficace : il faut se méfier des appels recalculés.

🎯 Accompagnement Majorant

Savoir dire si un algorithme récursif est rapide ou lent, c'est ce qui départage les copies. Nos mentors t'apprennent à compter les appels et à repérer d'un coup d'œil une récursion qui recalcule — le genre d'analyse qui rapporte gros à l'oral comme à l'écrit.

Trouver un mentor →

6. Récursivité et diviser pour régner

La récursivité est le langage naturel de la stratégie « diviser pour régner » : résoudre un problème en le coupant en sous-problèmes de même nature, plus petits, résolus récursivement, puis en recombinant leurs résultats.

💡 Le lien avec la dichotomie. La recherche par dichotomie dans un tableau trié (vue dans une autre fiche) en est l'exemple parfait : chercher dans t[g..d] revient à chercher dans une seule moitié de t[g..d]. Le cas de base est l'intervalle vide (g > d) ; le cas récursif relance la recherche sur la bonne moitié. Comme la taille est divisée par deux à chaque appel, la profondeur de récursion est en

O (lo g n)

— bien plus économe que Fibonacci. C'est le même fil rouge partout : trouver « ce qui décroît » (le variant) est le bon réflexe devant n'importe quelle fonction récursive.

7. Exercices d'application

Fais-les sur papier (déroule la pile !) avant d'ouvrir le corrigé, puis passe au quiz en bas de fiche.

Exo 1Repérer le cas de baseFacile

Dans la fonction ci-dessous, identifie le cas de base et le cas récursif, puis dis ce que calcule mystere(4).

def mystere(n):
    if n == 1:
        return 1
    return n + mystere(n - 1)

Voir la correction détaillée

Cas de base : n == 1 renvoie 1 (sans appel). Cas récursif : n + mystere(n - 1), sur n - 1 plus petit.

La fonction calcule

1 + 2 + \dots + n

. Pour n = 4 : 4 + 3 + 2 + 1.

Résultat : 10. (Attention : si on appelle mystere(0), le cas de base n == 1 est sauté et n décroît vers les négatifs → RecursionError.)

Exo 2Compter les élémentsIntermédiaire

Sur le modèle de la fonction somme, écris une fonction récursive longueur(t) qui renvoie le nombre d'éléments d'une liste, sans utiliser len.

Voir la correction détaillée

Cas de base : une liste vide a 0 élément. Cas récursif : une liste non vide a « 1 + le nombre d'éléments du reste ».

def longueur(t):
    if t == []:
        return 0
    return 1 + longueur(t[1:])

Le variant est la longueur de t : elle décroît de 1 à chaque appel (t[1:] est plus court), donc on atteint [] : la fonction termine.

Exo 3Corriger une récursion infinieDifficile

Cette fonction, censée calculer $x^{n}$ (avec n entier positif), lève une RecursionError. Trouve les deux erreurs et corrige-la.

def puissance(x, n):
    if n == 1:
        return 1
    return x * puissance(x, n)

Voir la correction détaillée

Erreur 1 — le cas récursif ne décroît pas : on rappelle puissance(x, n) avec le même n. L'argument ne se rapproche jamais du cas de base → récursion infinie. Il faut n - 1.

Erreur 2 — mauvais cas de base :

x^{1} = x

, pas 1. Et si on part de n = 0, le cas n == 1 n'est jamais atteint. Le bon cas de base est n == 0 qui renvoie 1 (car

x^{0} = 1

def puissance(x, n):
    if n == 0:
        return 1
    return x * puissance(x, n - 1)

Vérification : puissance(2, 5) donne 2 * 2 * 2 * 2 * 2 * 1 = 32.

Récap final — Ce qu'il faut absolument retenir

À la veille d'une khôlle ou d'un DS, parcours cette checklist : tu dois pouvoir répondre « oui, sans hésiter » à chaque question.

Sais-tu définir une fonction récursive, et nommer ses deux ingrédients (cas de base, cas récursif) ?
Sais-tu écrire la factorielle récursive de mémoire ?
Sais-tu dérouler une pile d'appels (descente puis remontée) sur un petit exemple ?
Sais-tu expliquer pourquoi une récursion termine (le variant entier positif qui décroît) ?
Sais-tu ce qui provoque une RecursionError et comment l'éviter ?
Sais-tu écrire une fonction récursive simple sur une liste (somme, longueur) ?
Sais-tu pourquoi Fibonacci récursif naïf est exponentiel (appels recalculés) ?
Sais-tu relier récursivité et « diviser pour régner » (exemple : la dichotomie) ?

À savoir refaire

Terminaison d'une récursion — variant entier positif n strictement décroissant, borné par 0.

Vue d'ensemble

Prérequis

1. Définition : cas de base et cas récursif

2. Exemple canonique : la factorielle

3. Pourquoi ça termine (et quand ça boucle)

4. Un deuxième exemple : la somme d'une liste

5. Le piège du coût : Fibonacci récursif naïf

6. Récursivité et diviser pour régner

7. Exercices d'application

Récap final — Ce qu'il faut absolument retenir

À savoir refaire

Débloque la fiche complète

Quiz — Récursivité

Fiches associées

Recherche par dichotomie

Variables, types et affectations

Conditions et booléens

Boucles for et while

Fonctions : paramètres et valeurs de retour

Listes et chaînes de caractères

Tu veux aller plus loin sur ce chapitre ?