Prepa Help
Prepa Help › Cours › Informatique, 1re année

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

Fonctions récursives : cas de base et appel récursif, pile d'appels et arbre des appels, terminaison, récursivité et itération, exemples classiques (factorielle, puissance rapide, dichotomie, Hanoï).

Les nombres sont ceux du chapitre complet ; chaque filière voit la partie qui correspond à son programme.

Une fonction récursive est une fonction qui s'appelle elle-même sur une donnée plus petite, jusqu'à un cas de base résolu sans appel. Elle sert à traduire directement une définition par récurrence et à écrire les algorithmes qui coupent en deux : dichotomie, puissance rapide, tours de Hanoï, parcours de structures imbriquées. Le chapitre est au programme d'informatique de première année en MPSI, PCSI, PTSI, TSI et TPC, au Maroc et en France ; les sujets du CNC, de CCINP, de Mines-Ponts et de X-ENS posent des questions de récursivité, reprises dans les exercices. Tu y trouves la récursivité en Python écrite en trois temps, la pile d'appels, la terminaison et la complexité d'une fonction récursive.

Ce que tu sauras faire

Une fonction récursive résout un problème en s'appelant elle-même sur un problème plus petit. Cette façon de penser simplifie tous les problèmes qui contiennent des copies plus petites d'eux-mêmes : une palmeraie divisée en parcelles, une recherche dans une liste triée, un arbre, une figure qui se répète. À la fin de ce chapitre, tu dois savoir :

L'essentiel : Écrire une fonction récursive Extrait gratuit

Un extrait de la fiche « L'essentiel » du chapitre. Les démonstrations sont dans le cours détaillé.

À retenir Les trois temps
  1. La variable sur laquelle on récurse, qui diminue d'un appel à l'autre.
  2. Le cas de base : la plus petite valeur, résolue sans appel.
  3. Le cas récursif : on suppose les appels plus petits justes, et l'on en déduit la réponse.

Pour une fonction qui renvoie une valeur, le résultat de l'appel se renvoie : return n * fact(n - 1), jamais l'appel seul. Une variable locale est recréée à chaque appel.

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

Une méthode du chapitre Extrait gratuit

Méthode Écrire une fonction récursive en trois temps
Quand l’utiliser

L'énoncé demande une fonction « récursive », ou le problème contient une copie plus petite de lui-même : une parcelle formée de parcelles, une liste privée de son premier élément, un entier divisé par 10.

Rappel de cours

Une fonction récursive a un ou plusieurs cas de base, résolus sans appel, et un cas récursif, qui se ramène à des données plus petites par des appels à elle-même. Dans le cas récursif, on suppose que les appels plus petits renvoient le bon résultat.

Démarche
  1. Choisir la variable sur laquelle on récurse et dire en quoi elle diminue d'un appel à l'autre.
  2. Écrire le cas de base : la plus petite valeur, et sa réponse.
  3. Écrire le cas récursif : « si je connais la réponse pour la donnée plus petite, comment en déduire la réponse ? »
  4. Vérifier à la main le cas de base, puis la valeur juste au-dessus.
Rédaction type
def f(n):
    if n == 0:                    # cas de base
        return ...
    return ... f(n - 1) ...       # cas récursif

« On récurse sur nn. Cas de base : pour n=0n = 0, [réponse]. Cas récursif : pour n≥1n \geq 1, [relation], et l'appel f(n - 1) porte sur un entier plus petit. »

Exemple traité

Calculer le produit a×ba \times b, pour bb entier naturel, par des additions : a×0=0a \times 0 = 0 et a×b=a+a×(b−1)a \times b = a + a \times (b - 1).

def produit(a, b):
    # a : nombre ; b : entier naturel
    # renvoie a * b, calculé par additions
    if b == 0:                    # cas de base
        return 0
    return a + produit(a, b - 1)  # cas récursif

print(produit(4, 3), produit(7, 0))

Le programme affiche :

12 0

On récurse sur bb : chaque appel retire 1 à bb, et le cas de base b=0b = 0 est atteint après bb appels.

Erreurs fréquentes
  • Commencer par le cas récursif et oublier le cas de base. Les correcteurs du concours Mines-Ponts (rapport 2020, informatique commune) écrivent, pour une fonction récursive à écrire : « Le cas de base a souvent été oublié ou mal traité. »
  • Faire porter l'appel sur la même donnée (produit(a, b) dans son propre corps) : la fonction s'appelle sans fin.
  • Écrire une boucle dans la fonction alors que l'énoncé demande la récursion.
Pour s’entraîner

Exercices 1, 3, 9, 10, 18 et 26, problèmes 1 et 4.

Un exercice corrigé Extrait gratuit

Exercice Quatre fonctions en trois temps ★☆☆

Pour chacune des quatre fonctions suivantes, dire sur quelle variable porte la récursion, écrire le cas de base et le cas récursif, puis écrire la fonction en Python.

  1. somme_entiers(n) renvoie 0+1+⋯+n0 + 1 + \dots + n pour un entier naturel nn.
  2. somme_carres_rec(n) renvoie S(n)=02+12+⋯+n2S(n) = 0^2 + 1^2 + \dots + n^2. Que vaut somme_carres_rec(5) ?
  3. compte_zeros(n) renvoie le nombre de chiffres 0 dans l'écriture décimale de l'entier naturel nn. Par exemple, compte_zeros(102030) vaut 3 et compte_zeros(0) vaut 1.
  4. symetrique(L, i, j) renvoie True si la portion L[i], ..., L[j] d'une liste se lit de la même façon dans les deux sens (comme un palindrome), False sinon, sans construire de tranche ; on l'appelle avec i=0i = 0 et j=j = len(L) - 1. Tester sur [1, 2, 3, 2, 1], [4, 7, 7, 4] et [1, 2].
Indications
  • Méthode 1 : la variable de la récursion est l'entier nn ; on suppose le problème résolu pour un entier plus petit.
  • Méthode 2 : S(0)=0S(0) = 0 et S(n)=n2+S(n−1)S(n) = n^2 + S(n-1).
  • Question 3 : le dernier chiffre de nn est n % 10, et les autres chiffres forment l'entier n // 10.
  • Question 4, méthode 12 : la variable de la récursion est la longueur j−i+1j - i + 1 de la portion ; on compare les deux bouts, puis on rapproche ii et jj.
Correction détaillée

Analyse. On remplit pour chaque fonction les trois temps de la méthode 1.

fonction variable cas de base cas récursif
somme_entiers nn n=0n = 0 : 0 nn + somme_entiers(n - 1)
somme_carres_rec nn n=0n = 0 : 0 n2n^2 + somme_carres_rec(n - 1)
compte_zeros nn n<10n < 10 : 1 si n=0n = 0, 0 sinon (1 si n % 10 vaut 0) + compte_zeros(n // 10)
symetrique j−i+1j - i + 1 i≥ji \geq j : True L[i] égal à L[j], et symetrique(L, i + 1, j - 1)

Pour compte_zeros, le cas de base est un nombre à un seul chiffre ; on ne peut pas s'arrêter à n=0n = 0, sinon compte_zeros(5) appellerait compte_zeros(0) et compterait un zéro qui n'est pas écrit.

def somme_entiers(n):
    # n : entier naturel ; renvoie 0 + 1 + ... + n
    if n == 0:                    # cas de base
        return 0
    return n + somme_entiers(n - 1)

def somme_carres_rec(n):
    # n : entier naturel ; renvoie 0² + 1² + ... + n²
    if n == 0:
        return 0
    return n * n + somme_carres_rec(n - 1)

def compte_zeros(n):
    # n : entier naturel ; renvoie le nombre de
    # chiffres 0 dans l'écriture décimale de n
    if n < 10:                    # un seul chiffre
        if n == 0:
            return 1
        return 0
    if n % 10 == 0:
        return 1 + compte_zeros(n // 10)
    return compte_zeros(n // 10)

def symetrique(L, i, j):
    # L : liste ; i, j : indices
    # renvoie True si L[i], ..., L[j] se lit de la même
    # façon dans les deux sens (True si i >= j)
    if i >= j:                    # zéro ou un élément
        return True
    if L[i] != L[j]:
        return False
    return symetrique(L, i + 1, j - 1)

print(somme_entiers(100), somme_carres_rec(5))
print(compte_zeros(102030), compte_zeros(7))
print(compte_zeros(0))
for L in [[1, 2, 3, 2, 1], [4, 7, 7, 4], [1, 2]]:
    print(symetrique(L, 0, len(L) - 1))

Le programme affiche :

5050 55
3 0
1
True
True
False

Chaque fonction s'arrête : dans les deux premières, nn est un entier naturel qui diminue de 1 à chaque appel jusqu'à 0 ; dans la troisième, pour n≥10n \geq 10, on a n // 10 <n< n, et l'entier atteint un nombre à un seul chiffre ; dans la quatrième, la longueur j−i+1j - i + 1 diminue de 2 à chaque appel, jusqu'à 0 ou 1 (cas de base i≥ji \geq j, qui couvre les longueurs paire et impaire).

Interprétation : 5050=100×10125050 = \frac{100 \times 101}{2} et 55=1+4+9+16+2555 = 1 + 4 + 9 + 16 + 25 ; les deux premières fonctions retrouvent les formules connues. compte_zeros(102030) fait 6 appels, un par chiffre.

Méthodes à retenir

Avant d'écrire, on remplit les trois temps : variable, cas de base, cas récursif. Le cas de base se choisit sur la plus petite entrée qui a un sens (un nombre à un chiffre, une portion de liste d'au plus un élément). Sur une liste, deux indices qui se rapprochent évitent toute copie. Voir les méthodes 1, 2 et 12.

Dans le chapitre complet

Le cours détaillé, toute la fiche « L'essentiel », 21 méthodes, 20 pièges corrigés, la carte mentale, 37 exercices corrigés, 4 problèmes de concours, les fiches à mémoriser et l'assistant qui répond à tes questions. Ce chapitre est offert : il s’ouvre en entier avec un compte d’essai gratuit.

Ouvrir l'essai gratuit

Plan du cours

Les méthodes du chapitre

Chaque méthode est une fiche : quand l'utiliser, le rappel de cours, les étapes, la rédaction attendue sur la copie, un exemple traité, les erreurs à éviter.

  1. Écrire une fonction récursive en trois temps
  2. Traduire une définition par récurrence en fonction récursive
  3. Choisir et vérifier les cas de base
  4. Construire le résultat avec la valeur renvoyée par l'appel
  5. Respecter une signature imposée avec une fonction auxiliaire
  6. Prévoir le résultat d'un appel : descente, puis remontée
  7. Dresser le tableau des états de la pile d'appels
  8. Dessiner l'arbre des appels et compter les appels
  9. Prévoir l'ordre des affichages
  10. Justifier la terminaison
  11. Prouver la correction par récurrence
  12. Récurser sur une liste ou une chaîne : indice ou tranche
  13. Parcourir une structure imbriquée
  14. Écrire une dichotomie récursive à deux bornes
  15. Écrire la puissance rapide et compter ses multiplications
  16. Compter les appels et les opérations d'une fonction récursive
  17. Éviter la limite de la pile
  18. Passer de l'itératif au récursif, et inversement
  19. Énumérer toutes les sous-listes ou toutes les permutations
  20. Fixer des bornes par défaut et compter les appels avec une variable globale
  21. Parcourir une liste imbriquée quelconque avec isinstance

Les exercices corrigés

Chaque exercice a ses indications, sa correction rédigée et ce qu'il faut en retenir.

Application directe (15)

Entraînement (16)

Approfondissement (6)

Les problèmes de concours

Des extraits de sujets réels, corrigés en entier, avec la durée conseillée et les méthodes mobilisées.

Questions fréquentes

Comment écrire une fonction récursive en Python ?

En trois temps. On choisit la variable sur laquelle on récurse, qui diminue d'un appel à l'autre. On écrit le cas de base, la plus petite valeur, résolue sans appel. On écrit le cas récursif en supposant les appels plus petits justes. Pour une fonction qui renvoie une valeur, on renvoie le résultat de l'appel : return n * fact(n - 1), jamais l'appel seul.

Qu'est-ce que la pile d'appels en récursivité ?

Chaque appel a ses propres variables locales, et l'appelant attend la valeur renvoyée. Les appels en attente sont empilés : le dernier commencé est le premier terminé. L'exécution descend jusqu'au cas de base, puis les valeurs remontent. Un print placé avant l'appel récursif s'exécute à la descente ; placé après, il s'exécute à la remontée, dans l'ordre inverse.

Que veut dire RecursionError: maximum recursion depth exceeded ?

Python a dépassé le nombre d'appels en attente qu'il accepte : sys.getrecursionlimit() vaut 1000. Cela arrive quand le cas de base n'est jamais atteint, parce qu'il manque ou que la variable ne diminue pas. Si la fonction est juste mais demande de l'ordre de 1000 appels en attente ou plus, on écrit une boucle à la place ; une copie de concours n'emploie pas sys.setrecursionlimit.

Comment prouver qu'une fonction récursive termine ?

On exhibe un variant : pour toute entrée permise, chaque appel porte sur une quantité entière, positive ou nulle, strictement plus petite, et les cas de base couvrent les plus petites valeurs. La correction se prouve ensuite par récurrence sur cette quantité : l'initialisation correspond au cas de base, l'hérédité au cas récursif. On utilise une récurrence forte quand l'appel porte sur n//2n // 2 ou sur une sous-structure.

Quelle est la complexité d'une fonction récursive ?

On compte le nombre d'appels, qui mesure le travail, et la profondeur, qui mesure la place dans la pile. C(n)=C(n−1)+1C(n) = C(n - 1) + 1 donne un coût linéaire, comme fact ; C(n)=C(n//2)+1C(n) = C(n // 2) + 1 un coût logarithmique, comme la puissance rapide ou la dichotomie ; C(n)=2C(n−1)+1C(n) = 2C(n - 1) + 1 un coût exponentiel, comme Hanoï. fib(30) fait 2 692 537 appels, mais au plus 30 en attente.

Quelle différence entre récursivité simple, double et mutuelle ?

Une récursivité simple fait au plus un appel récursif par exécution, comme fact ou la puissance rapide. Une récursivité double, ou multiple, fait deux appels ou plus, comme fib ou hanoi. Une récursivité mutuelle, ou croisée, met en jeu deux fonctions qui s'appellent l'une l'autre, comme est_pair et est_impair.

Comment y accéder

Ce chapitre fait partie des chapitres offerts : il s'ouvre en entier avec un compte d'essai gratuit. Créer un compte d'essai ou se connecter. Pour l'accès complet, les tarifs ou une question, écris-nous sur WhatsApp.

Toute ta prépa au même endroit

Pour chaque chapitre : le cours, l'essentiel, les méthodes, les pièges, les exercices corrigés, les problèmes de concours, et un assistant qui répond à tes questions. Programmes du Maroc et de France.

Essayer gratuitement Prepa Help

← Bases de Python : expressions, types, instructions, fonctions