La récursivité en prépa : principe et exemples

La récursivité déroute au premier contact : une fonction qui s'appelle elle-même, cela ressemble à un serpent qui se mord la queue. Puis on comprend l'idée maîtresse, et beaucoup de programmes deviennent d'un coup plus courts et plus clairs qu'en boucle. Une poupée russe contient une poupée plus petite, qui en contient une plus petite, jusqu'à la dernière qu'on ne peut plus ouvrir : c'est exactement une fonction récursive, avec sa descente et son point d'arrêt.

Cet article te donne tout ce qu'il faut pour maîtriser la récursivité en prépa, en informatique pour tous comme en option info : la définition rigoureuse (cas de base et cas récursif), le déroulé sur la pile d'appels, les grands classiques codés et commentés (factorielle, somme, puissance, Fibonacci, PGCD d'Euclide, parcours), la comparaison récursivité contre itération avec le piège du débordement de pile, le lien naturel avec les arbres, la preuve de terminaison, et trois exercices corrigés. Nos profs Hadamard, anciens de MP2I et de MPSI option info passés par l'X, l'ENS et CentraleSupélec, voient revenir chaque année les mêmes erreurs de cas de base : on les liste pour que tu les évites.

Cas de base et cas récursif

Une fonction récursive est une fonction qui s'appelle elle-même dans sa propre définition. Pour être correcte, elle doit toujours combiner deux ingrédients, jamais un seul :

L'exemple canonique est la factorielle. Mathématiquement, $n! = n \times (n-1)!$ avec $0! = 1$. Cette définition est déjà récursive : le cas de base est $0! = 1$, le cas récursif est $n! = n \times (n-1)!$. La traduction en Python est immédiate.

def factorielle(n):
    if n == 0:              # cas de base : 0! = 1, on arrête la descente
        return 1
    return n * factorielle(n - 1)   # cas récursif : n! = n * (n-1)!

L'argument passe de n à n - 1 à chaque appel : on se rapproche du cas de base $0$. C'est la condition vitale. Une fonction récursive sans cas de base atteignable, ou dont l'argument ne décroît pas vers le cas de base, s'appelle indéfiniment.

La pile d'appels et le déroulé

Pour comprendre ce qui se passe vraiment, il faut suivre la pile d'appels. À chaque appel de fonction, le programme empile un contexte : les variables locales et l'endroit exact où reprendre le calcul une fois l'appel terminé. En récursivité, ces contextes s'empilent les uns sur les autres pendant la descente, puis se dépilent pendant la remontée.

Déroulons factorielle(3). On descend d'abord jusqu'au cas de base, en suspendant chaque multiplication en attente du résultat de l'appel plus profond :

Les exemples classiques du cours

Une poignée de fonctions récursives revient sans arrêt en prépa. Les maîtriser, c'est reconnaître le schéma « cas de base + réduction » sur n'importe quel énoncé. Toutes ont un cas de base explicite et un appel qui se rapproche de ce cas.

Somme des entiers de 0 à n

Même schéma que la factorielle, avec une addition : $S(n) = n + S(n-1)$ et $S(0) = 0$.

def somme(n):
    if n == 0:          # cas de base
        return 0
    return n + somme(n - 1)   # cas récursif

Puissance x^n

On exploite $x^n = x \times x^{\,n-1}$ avec $x^0 = 1$.

def puissance(x, n):
    if n == 0:          # cas de base : x^0 = 1
        return 1
    return x * puissance(x, n - 1)   # cas récursif

Cette version fait $n$ multiplications. On peut la rendre bien plus rapide par exponentiation rapide, en distinguant exposant pair et impair : $x^n = (x^{n/2})^2$ si $n$ est pair. Le nombre de multiplications tombe à environ $\log_2 n$.

def puissance_rapide(x, n):
    if n == 0:
        return 1
    demi = puissance_rapide(x, n // 2)   # calculé une seule fois
    if n % 2 == 0:
        return demi * demi
    return x * demi * demi

Suite de Fibonacci

La suite $F_0 = 0$, $F_1 = 1$, $F_n = F_{n-1} + F_{n-2}$ a deux cas de base et deux appels récursifs.

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

def fib_memo(n, memo={}):
    if n < 2:
        return n
    if n not in memo:            # on ne calcule qu'une seule fois
        memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

La mémoïsation est la porte d'entrée vers la programmation dynamique, un pan entier de l'algorithmique au programme d'option info.

PGCD par l'algorithme d'Euclide

L'algorithme d'Euclide est récursif par nature : $\mathrm{pgcd}(a, b) = \mathrm{pgcd}(b, a \bmod b)$, avec le cas de base $\mathrm{pgcd}(a, 0) = a$. Le reste décroît strictement à chaque appel, ce qui garantit qu'on atteint $0$.

def pgcd(a, b):
    if b == 0:          # cas de base
        return a
    return pgcd(b, a % b)   # cas récursif : le reste décroît vers 0

Parcours d'une liste

Une liste se voit récursivement comme « un premier élément, suivi du reste de la liste ». Le cas de base est la liste vide. Voici la somme des éléments d'un tableau, écrite récursivement.

def somme_liste(tab):
    if tab == []:       # cas de base : la somme d'une liste vide vaut 0
        return 0
    return tab[0] + somme_liste(tab[1:])   # premier + somme du reste

Ce découpage « tête + reste » est le socle de toute la manipulation récursive des structures linéaires, qu'on retrouve sur les structures de données de la prépa (listes, piles, files, arbres).

Récursivité contre itération

Tout ce qui se code en récursif se code aussi en itératif (avec une boucle), et réciproquement. Le concours attend que tu saches faire les deux et justifier ton choix. La factorielle en boucle, par exemple, ne construit aucune pile :

def factorielle_iterative(n):
    resultat = 1
    for k in range(2, n + 1):
        resultat = resultat * k
    return resultat

La règle pratique : récursif quand la structure du problème est récursive (un arbre, une division en sous-problèmes), itératif quand un simple parcours en ligne suffit. C'est exactement le genre d'arbitrage qu'on travaille en option informatique en MPSI.

Récursivité et arbres

C'est le domaine où la récursivité devient irremplaçable. Un arbre binaire est défini récursivement : il est soit vide, soit un nœud portant une valeur et deux sous-arbres qui sont eux-mêmes des arbres binaires. Cette définition récursive appelle un traitement récursif. Représentons un arbre par un triplet (valeur, gauche, droite), l'arbre vide par None.

# Exemple : un arbre de racine 1, avec deux feuilles 2 et 3
arbre = (1, (2, None, None), (3, None, None))

def hauteur(a):
    if a is None:       # cas de base : l'arbre vide a une hauteur 0
        return 0
    valeur, gauche, droite = a
    return 1 + max(hauteur(gauche), hauteur(droite))

La structure de la fonction épouse la structure des données : un cas de base pour l'arbre vide, puis un appel récursif sur chaque sous-arbre, dont on combine les résultats. Compter les nœuds, additionner les valeurs, chercher un élément : tout suit ce même moule.

Prouver la terminaison

Une fonction récursive n'est correcte que si elle se termine : elle ne doit faire qu'un nombre fini d'appels. La technique attendue au concours est le variant.

Pour factorielle(n), le variant est $n$ : il passe de $n$ à $n-1$ à chaque appel et atteint $0$, le cas de base. Pour pgcd(a, b), le variant est $b$ : le second argument, le reste $a \bmod b$, est strictement inférieur à $b$, donc il décroît jusqu'à $0$. À chaque fois qu'on écrit une fonction récursive, on doit pouvoir nommer ce variant.

Trois exercices corrigés

Exercice 1, somme des chiffres d'un entier

Énoncé. Écrire une fonction récursive somme_chiffres(n) qui, pour un entier n positif, renvoie la somme de ses chiffres. Par exemple somme_chiffres(1234) vaut $10$.

Idée. Le dernier chiffre de n est n % 10 ; les chiffres restants forment n // 10. Le cas de base est un entier à un seul chiffre (n < 10), qui est sa propre somme de chiffres.

def somme_chiffres(n):
    if n < 10:          # cas de base : un seul chiffre
        return n
    return n % 10 + somme_chiffres(n // 10)   # dernier chiffre + le reste

Vérification. Sur somme_chiffres(1234) : $4 + (3 + (2 + 1)) = 10$. Le variant est le nombre de chiffres de n, qui décroît de $1$ à chaque appel : la fonction se termine.

Exercice 2, inverser une chaîne de caractères

Énoncé. Écrire une fonction récursive inverse(s) qui renvoie la chaîne s lue à l'envers. Par exemple inverse("prepa") vaut "aperp".

Idée. L'inverse d'une chaîne, c'est l'inverse de son reste (tout sauf le premier caractère), suivi de son premier caractère. Le cas de base est la chaîne vide, dont l'inverse est la chaîne vide.

def inverse(s):
    if s == "":         # cas de base : la chaine vide s'inverse en elle-meme
        return ""
    return inverse(s[1:]) + s[0]   # inverse du reste, puis le 1er caractere

Vérification. Sur inverse("abc") : inverse("bc") + "a", soit (inverse("c") + "b") + "a", soit "cba". Le variant est la longueur de s, qui décroît de $1$ à chaque appel jusqu'à la chaîne vide.

Exercice 3, compter les feuilles d'un arbre binaire

Énoncé. Un arbre binaire est représenté par un triplet (valeur, gauche, droite), l'arbre vide par None. Une feuille est un nœud sans sous-arbre (ses deux fils valent None). Écrire une fonction récursive nb_feuilles(a) qui compte les feuilles de l'arbre.

Idée. Deux cas de base : l'arbre vide n'a aucune feuille ; un nœud dont les deux fils sont vides est une feuille (il en compte $1$). Sinon, le nombre de feuilles est la somme des feuilles du sous-arbre gauche et du sous-arbre droit.

def nb_feuilles(a):
    if a is None:               # cas de base : arbre vide
        return 0
    valeur, gauche, droite = a
    if gauche is None and droite is None:   # cas de base : une feuille
        return 1
    return nb_feuilles(gauche) + nb_feuilles(droite)   # cas recursif

Vérification. Sur (1, (2, None, None), (3, None, None)) : la racine n'est pas une feuille, on additionne nb_feuilles du sous-arbre gauche (la feuille $2$, donc $1$) et du droit (la feuille $3$, donc $1$), total $2$. Le variant est la hauteur de l'arbre, qui décroît d'au moins $1$ à chaque appel : la fonction se termine.

Ce qu'il faut retenir

• Deux ingrédients obligatoires : un cas de base qui arrête la récursion, un cas récursif qui se rapproche du cas de base.
• La pile d'appels : on descend jusqu'au cas de base en empilant des contextes, puis on remonte en combinant les résultats.
• Les classiques : factorielle, somme, puissance (et exponentiation rapide), Fibonacci, PGCD d'Euclide, parcours « tête + reste ».
• Récursif ou itératif : récursif quand la structure est récursive (arbres, diviser-pour-régner), itératif pour un simple parcours linéaire, pour éviter le débordement de pile.
• Fibonacci naïf est exponentiel : la mémoïsation le rend linéaire et ouvre sur la programmation dynamique.
• La terminaison se prouve avec un variant, quantité entière positive qui décroît strictement vers le cas de base.

La récursivité est au cœur de l'informatique de prépa, en informatique pour tous comme en option info, et elle structure des filières entières comme la MP2I. Bien la comprendre, c'est gagner en aisance sur les arbres, le diviser-pour-régner et la programmation dynamique, qui en découlent directement.

Si un point coince, un déroulé sur papier de la pile d'appels ou un choix récursif contre itératif, un regard d'ancien taupin passé par l'informatique fait souvent gagner du temps. Nos profs Hadamard peuvent t'aider à cadrer ta pratique et tes révisions d'algorithmique.