Récursivité en Python : exercices corrigés de prépa MPSI

Une fonction récursive a un cas de base, résolu sans appel, et un cas récursif qui s'appelle sur une donnée strictement plus petite. Elle termine si une quantité entière positive, le variant, diminue strictement à chaque appel jusqu'au cas de base ; sa correction se prouve par récurrence sur cette quantité. Sa complexité se lit sur une relation de récurrence tirée du code, par exemple $C(n) = C(n - 1) + 1$ pour un coût linéaire.

Le chapitre est au programme de première année en MPSI, PCSI, PTSI, TSI et TPC, au Maroc comme en France.

Quelles relations de récurrence faut-il reconnaître ?

On note $C(n)$ le nombre d'appels pour une donnée de taille $n$ ; la relation se lit sur le code.

Le nombre d'appels écrits dans le code ne donne pas le coût : fib en contient deux et coûte un temps exponentiel. On regarde aussi la profondeur, le nombre d'appels en attente : fib(30) fait plus de deux millions d'appels, mais jamais plus de 30 dans la pile.

Méthode en cinq étapes

1. Écrire. Choisir la variable sur laquelle on récurse, écrire le cas de base (0, la liste vide, la zone vide), puis le cas récursif en supposant les appels plus petits justes, et renvoyer le résultat par return.
2. Prouver la terminaison. Nommer le variant ($n$, len(L) - i, $d - g$), entier et positif pour toute entrée permise, et montrer qu'il diminue strictement à chaque appel.
3. Prouver la correction. Récurrence sur le variant : l'initialisation est le cas de base, l'hérédité le cas récursif. Quand l'appel porte sur $n // 2$ ou sur une sous-structure, récurrence forte.
4. Évaluer la complexité. Écrire la relation sur $C(n)$, la calculer sur quelques valeurs, puis ajouter le travail de chaque appel (une tranche coûte sa longueur).
5. Vérifier la profondeur. sys.getrecursionlimit() vaut 1000 par défaut, programme principal compris : au-delà de quelques centaines d'appels en attente, on écrit une boucle.

Exercice 1 : compter les éléments pairs d'une liste

Écrire une fonction récursive nb_pairs(L) qui renvoie le nombre d'éléments pairs d'une liste d'entiers, sans tranche. Prouver sa terminaison et sa correction, compter ses appels, puis comparer avec une version par tranches.

On récurse sur un indice $i$ dans une fonction auxiliaire ; nb_pairs garde la signature demandée.

def nb_pairs_depuis(L, i):
    # nombre d'éléments pairs parmi L[i], ..., L[len(L) - 1]
    if i == len(L):               # cas de base
        return 0
    reste = nb_pairs_depuis(L, i + 1)
    if L[i] % 2 == 0:
        return 1 + reste
    return reste

def nb_pairs(L):
    return nb_pairs_depuis(L, 0)

print(nb_pairs([4, 7, 10, 3, 8]), nb_pairs([]), nb_pairs([1, 3]))

Le programme affiche :

3 0 0

Terminaison. len(L) - i est un entier positif ou nul, qui diminue de 1 à chaque appel : il atteint 0, le cas de base.

Correction. Récurrence sur $k =$ len(L) - i. Pour $k = 0$, la zone est vide et la fonction renvoie 0. Pour $k \geq 1$, si l'appel sur i + 1 renvoie le nombre de pairs à partir de L[i + 1], la fonction y ajoute 1 exactement quand L[i] est pair.

Complexité. $C(0) = 1$ et $C(k) = C(k - 1) + 1$ : $n + 1$ appels pour $n$ éléments, chacun à coût constant, donc un coût linéaire. La profondeur vaut aussi $n + 1$ : nb_pairs([2] * 500) renvoie 500, mais nb_pairs([2] * 2000) s'arrête sur RecursionError.

Version par tranches. Même nombre d'appels, mais chaque tranche recopie la liste restante : $\frac{n(n-1)}{2}$ copies en tout, 404 550 pour $n = 900$. Le coût devient quadratique.

Exercice 2 : racine carrée entière par dichotomie

Pour un entier naturel $n$, on cherche l'entier $r$ tel que $r^2 \leq n < (r + 1)^2$. Écrire une fonction récursive racine_entre(n, g, d) qui, si $g < d$ et $g^2 \leq n < d^2$, renvoie $r$ en coupant l'intervalle en deux. Prouver sa terminaison et sa correction, puis compter ses appels.

def racine_entre(n, g, d):
    # hypothèse : g < d et g * g <= n < d * d
    if d - g == 1:                # cas de base
        return g
    m = (g + d) // 2              # g < m < d
    if m * m <= n:
        return racine_entre(n, m, d)
    return racine_entre(n, g, m)

def racine(n):
    return racine_entre(n, 0, n + 1)

print(racine(0), racine(10), racine(16), racine(10 ** 6))

Le programme affiche :

0 3 4 1000

L'appel de départ vérifie l'hypothèse : $0 \leq n < (n + 1)^2$.

Terminaison. Le variant est $d - g \geq 1$. Si $d - g \geq 2$, alors $g < m < d$ : l'appel porte sur $(m, d)$ ou $(g, m)$, de largeur strictement plus petite, jusqu'à $d - g = 1$.

Correction. Récurrence forte sur $d - g$. Si $d - g = 1$, l'hypothèse s'écrit $g^2 \leq n < (g + 1)^2$ : $g$ est la réponse. Sinon, le couple $(m, d)$ si $m^2 \leq n$, ou $(g, m)$ si $n < m^2$, vérifie encore l'hypothèse, et l'appel renvoie la bonne valeur.

Complexité. La largeur part de $n + 1$ et devient $\lfloor w/2 \rfloor$ ou $\lceil w/2 \rceil$ : au pire $C(w) = C(\lceil w/2 \rceil) + 1$, une croissance logarithmique. Une fonction de comptage donne 21 appels pour $n = 10^6$ et 41 pour $10^{12}$, contre environ $\sqrt n$ essais en testant $r = 0, 1, 2, \dots$.

Quelles sont les erreurs classiques ?

• Un cas de base absent ou trop étroit. fib avec les seuls cas $n = 1$ et $n = 2$, appelée sur 0, descend vers $-1, -2, \dots$ jusqu'à RecursionError. Une relation d'ordre 2 demande deux cas de base : if n < 2: return n.
• Le return oublié devant l'appel. La fonction renvoie None, et l'appel du dessus échoue sur une TypeError.
• Un appel qui ne rapetisse pas la donnée. Chercher dans [m, d] au lieu de [m + 1, d] laisse une zone d'un élément se rappeler sans fin.
• Des tranches à chaque appel. Elles recopient la liste ; une dichotomie par tranches n'est plus logarithmique.
• Deux appels identiques au lieu d'une variable. Dans la puissance rapide, y = puissance_rapide(x, n // 2), puis y * y.
• Relever la limite de la pile par sys.setrecursionlimit sur une copie, au lieu d'écrire une boucle.

En TSI et TPC en France, la puissance rapide n'est pas citée par le programme : elle sert d'exemple sans être exigible. Le programme marocain ajoute les arguments par défaut, le comptage des appels par une variable global et le test isinstance sur les listes imbriquées.

Questions fréquentes

Comment calculer la complexité d'une fonction récursive ?

On écrit la relation sur le nombre d'appels $C(n)$ en lisant le code, puis on ajoute le travail de chaque appel. $C(n) = C(n - 1) + 1$ donne un coût linéaire, $C(n) = C(n // 2) + 1$ logarithmique, $C(n) = 2C(n - 1) + 1$ exponentiel.

Comment prouver qu'une fonction récursive termine ?

On exhibe un variant : une quantité entière, positive ou nulle pour toute entrée permise, qui diminue strictement à chaque appel, avec des cas de base qui couvrent les plus petites valeurs. « La fonction a un cas de base » ne suffit pas : il faut montrer que les appels y arrivent.

Que veut dire RecursionError: maximum recursion depth exceeded ?

Python a dépassé le nombre d'appels en attente qu'il accepte : environ 1000 par défaut, le programme principal compris. Soit le cas de base n'est jamais atteint, soit la fonction est juste mais trop profonde : on écrit alors une boucle.

Pour aller plus loin

Le chapitre « Récursivité » d'informatique de sup, pour MPSI, PCSI, PTSI, TSI et TPC, reprend la pile d'appels, Hanoï, les fractales et plus de trente exercices corrigés ; sa page publique montre un extrait et le plan. Il fait partie des chapitres offerts et s'ouvre en entier avec l'essai gratuit. Pour une question sur un exercice, tu peux écrire sur WhatsApp.