Numérique et sciences informatiques (spécialité) · TerminaleBac

Récursivité : exercices corrigés de NSI en Terminale

Publié le 7 novembre 2026 · Mis à jour le 7 novembre 2026 · Signaler une erreur

L'essentiel

Une fonction récursive s'appelle elle-même ; sans cas de base (condition d'arrêt), elle ne se termine pas.¹
Pour chaque fonction, pose trois questions : quel est le cas de base, comment le problème diminue-t-il à chaque appel, comment combine-t-on le résultat de l'appel ?
Pour comprendre un programme, déroule la trace : liste les appels, descends jusqu'au cas de base, puis remonte en calculant.
Pour compter les appels, définis une petite relation de récurrence et calcule-la de proche en proche.
Une version récursive peut être plus lente que sa version itérative.¹

Comment utiliser ces exercices

Ces exercices t'entraînent à lire, écrire et analyser des fonctions récursives, comme on te le demande en spécialité NSI. Au bac, l'épreuve écrite dure 3 h 30, sans calculatrice, et comporte 3 exercices ; dans certains sujets, un exercice entier porte sur la récursivité.² Tu dois donc savoir dérouler un programme à la main, sans machine.

Cherche d'abord seul, sur papier. Ouvre les indices un par un, puis seulement après compare avec la correction. Les exercices sont rangés par difficulté croissante : les premiers fixent le réflexe de la trace, les derniers demandent de raisonner sur le nombre d'appels et de réparer du code.

Cas de baseRepère la valeur qui répond sans nouvel appel.
DescenteNote chaque appel jusqu'au cas de base.
RemontéeCalcule en revenant, appel après appel.
ContrôleCompare avec une formule ou un cas simple.

Dérouler une fonction récursive à la main · La trace d'une fonction récursive se fait en deux temps : on descend, puis on remonte.

Rappels utiles avant de commencer

Pour s'auto-évaluer

Les exercices

Exercice 1 Factorielle : dérouler la trace

★☆☆Environ 8 min

On considère la fonction suivante.

def fact(n):
    if n == 0:
        return 1
    return n * fact(n - 1)

Quel est le cas de base ?
Écris la suite des appels déclenchés par fact(5), puis calcule la valeur renvoyée.

Indice 1

Descends d'abord jusqu'à fact(0), sans calculer.

Indice 2

Remonte ensuite : chaque appel multiplie son n par le résultat de l'appel en dessous.

Voir la correction pas à pas

Le cas de base est n == 0 : la fonction renvoie 1 sans nouvel appel.
Appels descendants : fact(5) appelle fact(4), qui appelle fact(3), puis fact(2), fact(1), fact(0).
fact(0) renvoie 1.
Remontée : fact(1) = 1 * 1 = 1, fact(2) = 2 * 1 = 2, fact(3) = 3 * 2 = 6, fact(4) = 4 * 6 = 24.
Enfin fact(5) = 5 * 24 = 120.

fact(5) renvoie 120. La descente prépare les calculs, la remontée les effectue : retiens ce schéma pour toutes les traces.

Exercice 2 Somme des entiers de 1 à n

★☆☆Environ 8 min

def somme(n):
    if n == 0:
        return 0
    return n + somme(n - 1)

Que renvoie somme(6) ? Vérifie ton résultat avec une formule de ton cours de mathématiques sur la somme des premiers entiers.

Indice 1

Même schéma que la factorielle, mais avec une addition.

Indice 2

La somme des entiers de 1 à $n$ vaut $\frac{n(n+1)}{2}$ .

Voir la correction pas à pas

Cas de base : somme(0) renvoie 0.
Descente : somme(6) appelle somme(5), puis somme(4), somme(3), somme(2), somme(1), somme(0).
Remontée : somme(1) = 1, somme(2) = 3, somme(3) = 6, somme(4) = 10, somme(5) = 15.
somme(6) = 6 + 15 = 21.
Contrôle : $\frac{6 \times 7}{2} = 21$ .

somme(6) renvoie 21, ce que confirme la formule. Une fonction récursive et une formule fermée donnent le même résultat : c'est un bon moyen de contrôler ton travail.

Exercice 3 Puissance : combien d'appels, quelle valeur ?

★☆☆Environ 10 min

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

Que renvoie puissance(3, 4) ?
Combien d'appels à puissance (le premier compris) sont exécutés pour calculer puissance(3, 4) ? Donne ce nombre en fonction de $n$ pour un appel puissance(x, n) avec $n \geq 0$ .

Indice 1

À chaque appel, $n$ diminue de 1 jusqu'à 0.

Indice 2

Compte les valeurs de $n$ rencontrées : 4, 3, 2, 1, 0.

Voir la correction pas à pas

Cas de base : puissance(x, 0) renvoie 1.
Remontée : puissance(3, 1) = 3 * 1 = 3, puissance(3, 2) = 9, puissance(3, 3) = 27, puissance(3, 4) = 81.
Les valeurs de $n$ rencontrées sont 4, 3, 2, 1 et 0 : cela fait 5 appels.
En général, les valeurs sont $n, n-1, \dots, 0$ : il y a $n + 1$ appels.

puissance(3, 4) renvoie 81 et exécute 5 appels, soit $n+1$ pour $n = 4$ . Le nombre d'appels croît linéairement avec $n$ : c'est un premier exemple de comptage du coût d'une fonction récursive.

Exercice 4 Somme des chiffres d'un entier

★★☆Environ 12 min

On veut additionner les chiffres de l'écriture décimale d'un entier positif.

def somme_chiffres(n):
    if n < 10:
        return n
    return n % 10 + somme_chiffres(n // 10)

Quel est le cas de base, et pourquoi la réponse y est-elle immédiate ?
Déroule somme_chiffres(2748).

Indice 1

n % 10 donne le dernier chiffre, n // 10 supprime ce dernier chiffre.

Indice 2

Écris la suite des arguments : 2748, puis 274, puis 27, puis 2.

Voir la correction pas à pas

Le cas de base est n < 10 : l'entier n'a qu'un chiffre, la somme de ses chiffres est lui-même.
Suite des arguments : 2748, 274, 27, 2. Le dernier vérifie n < 10.
somme_chiffres(2) renvoie 2.
somme_chiffres(27) = 7 + 2 = 9.
somme_chiffres(274) = 4 + 9 = 13.
somme_chiffres(2748) = 8 + 13 = 21.

Le résultat est 21. L'argument perd un chiffre à chaque appel : il finit forcément par être strictement inférieur à 10, ce qui garantit l'arrêt.

Exercice 5 Le PGCD par l'algorithme d'Euclide

★★☆Environ 12 min

def pgcd(a, b):
    if b == 0:
        return a
    return pgcd(b, a % b)

Déroule pgcd(84, 36) en notant chaque appel.
Pourquoi cette fonction se termine-t-elle toujours quand $a$ et $b$ sont des entiers naturels ?

Indice 1

Calcule 84 % 36, puis 36 modulo le reste obtenu.

Indice 2

Observe la suite des deuxièmes arguments : elle est strictement décroissante.

Voir la correction pas à pas

Premier appel : pgcd(84, 36). Comme b n'est pas nul, on calcule 84 % 36 = 12.
Deuxième appel : pgcd(36, 12). On calcule 36 % 12 = 0.
Troisième appel : pgcd(12, 0). Ici b == 0 : cas de base, on renvoie 12.
Terminaison : le deuxième argument de l'appel suivant est un reste de division par b, donc strictement inférieur à b.
Une suite d'entiers naturels strictement décroissante est finie : elle atteint 0, donc le cas de base.

pgcd(84, 36) renvoie 12, en 3 appels. L'argument de terminaison (une quantité entière positive qui décroît strictement) est celui qu'on attend de toi dans une preuve de terminaison.

Exercice 6 Maximum d'une liste

★★☆Environ 12 min

def maxi(L):
    if len(L) == 1:
        return L[0]
    m = maxi(L[1:])
    if m > L[0]:
        return m
    return L[0]

Quel est le cas de base ? Que se passerait-il avec une liste vide ?
Que renvoie maxi([7, -3, 12, 5, 9]) ? Écris les listes passées successivement en argument.

Indice 1

L[1:] est la liste privée de son premier élément.

Indice 2

Au fond de la pile, il ne reste qu'un élément.

Voir la correction pas à pas

Le cas de base est une liste à un seul élément : son maximum est cet élément.
Avec une liste vide, len(L) == 1 n'est jamais vrai et L[1:] reste vide : la fonction ne s'arrête jamais. Le cas de base doit être atteint pour toute entrée valable, d'où l'hypothèse d'une liste non vide.
Arguments successifs : [7, -3, 12, 5, 9], [-3, 12, 5, 9], [12, 5, 9], [5, 9], [9].
maxi([9]) renvoie 9. maxi([5, 9]) : 9 > 5, donc 9. maxi([12, 5, 9]) : 9 > 12 est faux, donc 12.
maxi([-3, 12, 5, 9]) : 12 > -3, donc 12. maxi([7, -3, 12, 5, 9]) : 12 > 7, donc 12.

La fonction renvoie 12. Remarque pratique : la liste raccourcit d'un élément à chaque appel, c'est ce qui rapproche l'argument du cas de base.

Exercice 7 Fibonacci : compter les appels

★★★Environ 15 min

On définit :

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Les cas de base sont donc fib(0) et fib(1).¹

Calcule fib(5).
Soit $C(n)$ le nombre total d'appels à fib (le premier compris) provoqués par fib(n). Justifie que $C(0) = C(1) = 1$ et que $C(n) = 1 + C(n-1) + C(n-2)$ pour $n \geq 2$ .
Calcule $C(5)$ .

Indice 1

Calcule les valeurs de fib(0) à fib(5) dans l'ordre, comme un tableau.

Indice 2

Pour $C(n)$ , calcule de proche en proche $C(2)$ , $C(3)$ , $C(4)$ , $C(5)$ .

Voir la correction pas à pas

Valeurs : fib(0) = 0, fib(1) = 1, fib(2) = 1, fib(3) = 2, fib(4) = 3, fib(5) = 5.
Pour $n = 0$ ou $n = 1$ , un seul appel est exécuté, car on est dans le cas de base : $C(0) = C(1) = 1$ .
Pour $n \geq 2$ , l'appel courant compte pour 1, auquel s'ajoutent tous les appels de fib(n - 1) et ceux de fib(n - 2) : $C(n) = 1 + C(n-1) + C(n-2)$ .
Calculs : $C(2) = 1 + 1 + 1 = 3$ ; $C(3) = 1 + 3 + 1 = 5$ ; $C(4) = 1 + 5 + 3 = 9$ ; $C(5) = 1 + 9 + 5 = 15$ .
Constat : fib(5) vaut 5 mais exige 15 appels, parce que les mêmes sous-calculs sont refaits (par exemple fib(3) est calculé deux fois).

Il y a 15 appels pour calculer fib(5). Ce gaspillage illustre qu'un programme récursif peut être plus lent que son équivalent itératif.¹ Une boucle qui garde en mémoire les deux dernières valeurs ne fait que quelques tours.

Exercice 8 Compter les déplacements d'un programme récursif

★★★Environ 15 min

Un programme affiche un message à chaque déplacement d'un disque dans un jeu de pile. La fonction deplacements(n) renvoie le nombre de messages affichés pour $n$ disques :

def deplacements(n):
    if n == 0:
        return 0
    return 2 * deplacements(n - 1) + 1

Calcule deplacements(n) pour $n$ de 0 à 5.
Conjecture une formule en fonction de $n$ .
Démontre la formule par récurrence.

Indice 1

Remplis un tableau avec les valeurs successives.

Indice 2

Compare chaque valeur à une puissance de 2.

Indice 3

Pour l'hérédité, remplace deplacements(n) par sa définition.

Voir la correction pas à pas

Valeurs : 0, 1, 3, 7, 15, 31 pour $n = 0, 1, \dots, 5$ .
Chaque valeur est une puissance de 2 moins 1 : on conjecture $d(n) = 2^n - 1$ .
Initialisation : $d(0) = 0 = 2^0 - 1$ .
Hérédité : on suppose $d(n) = 2^n - 1$ pour un entier $n \geq 0$ . Alors $d(n+1) = 2\,d(n) + 1 = 2(2^n - 1) + 1 = 2^{n+1} - 1$ .
Conclusion : par récurrence, $d(n) = 2^n - 1$ pour tout entier naturel $n$ . Pour $n = 5$ : $2^5 - 1 = 31$ .

deplacements(5) renvoie 31. Le lien est direct entre une fonction récursive et une suite définie par récurrence : le cas de base est l'initialisation, l'appel récursif est la relation de récurrence.

Exercice 9 Réparer une fonction qui ne s'arrête pas

★★★Environ 12 min

Un élève veut écrire une fonction qui compte combien de fois on peut retirer 2 à un entier $n \geq 0$ en restant positif ou nul.

def retraits(n):
    if n == 0:
        return 0
    return 1 + retraits(n - 2)

Que se passe-t-il pour retraits(4) ? Pour retraits(5) ?
Explique le défaut et propose une version corrigée.
Que renvoie ta version pour retraits(5) ?

Indice 1

Écris la suite des arguments pour retraits(5) : 5, 3, 1, ...

Indice 2

Un cas de base doit être atteint pour toutes les valeurs d'entrée permises.

Voir la correction pas à pas

retraits(4) : arguments 4, 2, 0. Le cas de base est atteint, le résultat est 2.
retraits(5) : arguments 5, 3, 1, -1, -3... L'argument saute par-dessus 0 et ne l'atteint jamais : la fonction ne se termine pas.
Défaut : le cas de base ne couvre que la valeur 0, alors que l'argument peut devenir 1 ou négatif.
Correction : tester n < 2 (ou n <= 1) comme cas de base : if n < 2: return 0.
Avec la correction, retraits(5) : arguments 5, 3, 1 ; retraits(1) renvoie 0, retraits(3) renvoie 1, retraits(5) renvoie 2.

Le cas de base doit être atteint par toute suite d'arguments possible, pas seulement par certaines. Sans cela, le programme ne se termine pas, ce qui peut arriver aussi avec une boucle.³ Le bon réflexe : écrire la suite des arguments pour une valeur paire et une valeur impaire.

Exercice 10 Palindrome sur une chaîne de caractères

★★★Environ 15 min

Un mot est un palindrome s'il se lit de la même façon dans les deux sens. On propose :

def est_palindrome(s):
    if len(s) <= 1:
        return True
    return s[0] == s[-1] and est_palindrome(s[1:-1])

Quels sont les cas de base ? Justifie qu'il n'y a pas de risque de boucle infinie.
Déroule est_palindrome("kayak"), puis est_palindrome("radio").
Dans quel cas l'appel récursif n'est-il pas effectué ? Explique pourquoi.

Indice 1

s[1:-1] retire le premier et le dernier caractère.

Indice 2

L'opérateur and n'évalue pas son second membre si le premier est faux.

Voir la correction pas à pas

Le cas de base est une chaîne de longueur 0 ou 1, qui est toujours un palindrome.
Terminaison : la longueur diminue de 2 à chaque appel. Elle finit par valoir 0 ou 1, ce qui donne bien un cas de base (ici, <= 1 couvre les deux parités).
"kayak" : 'k' == 'k' puis appel sur "aya" ; 'a' == 'a' puis appel sur "y" ; cas de base, True. Résultat : True, en 3 appels.
"radio" : 'r' == 'o' est faux ; avec and, l'appel sur "adi" n'est pas effectué. Résultat : False, en 1 seul appel.
Le premier test faux suffit à conclure : inutile de comparer le reste.

"kayak" est un palindrome, "radio" n'en est pas un. Ce programme travaille sur une chaîne qui raccourcit à chaque appel : c'est le type de programme récursif sur les chaînes que l'on rencontre souvent en cours.¹

Les questions qu'on se pose

Comment savoir si ma fonction récursive va bien s'arrêter ?

Vérifie deux choses. D'abord, il existe un cas de base qui ne fait aucun nouvel appel : ce sont les conditions d'arrêt.¹ Ensuite, à chaque appel, l'argument se rapproche d'un cas de base, par exemple un entier positif qui décroît strictement ou une liste qui raccourcit. Teste mentalement une valeur paire et une valeur impaire, une liste vide et une liste à un élément : ce sont les entrées où les oublis apparaissent.

Faut-il toujours préférer la récursivité à une boucle ?

Non. Une fonction récursive est souvent plus courte et plus proche de la définition mathématique, mais elle peut être plus lente que son équivalent itératif.¹ L'exercice sur Fibonacci le montre : les mêmes calculs sont refaits plusieurs fois. En revanche, pour des structures définies récursivement comme les arbres binaires, la récursivité est le moyen naturel de les parcourir.³

Comment m'y prendre le jour de l'épreuve de NSI ?

Au bac, le sujet compte trois exercices, sans calculatrice, et l'un d'eux peut porter entièrement sur la récursivité.² Écris toujours la trace des appels sur ton brouillon : descente jusqu'au cas de base, puis remontée avec les calculs. Cette trace te donne le résultat attendu et te permet de justifier chaque ligne de ta réponse.

Sources

Document d'accompagnement : Récursivité (PDF), Éduscol - Ministère de l'Éducation nationale. Consulté le 7 novembre 2026.
Spécialité NSI - Numérique et Sciences Informatiques (STI Éduscol), Éduscol STI - Ministère de l'Éducation nationale. Consulté le 7 novembre 2026.
Récursivité, Wikipédia. Consulté le 7 novembre 2026.
Récursivité (linguistique), Wikipédia. Consulté le 7 novembre 2026.

Les numéros dans le texte renvoient à ces sources. Une source qui ne dit pas ce qu'on lui fait dire ? Signale-le.

Signaler une erreur sur cette page

Récursivité : exercices corrigés de NSI en Terminale

L'essentiel

Comment utiliser ces exercices

Rappels utiles avant de commencer

Pour s'auto-évaluer

Les exercices

Exercice 1 Factorielle : dérouler la trace

Exercice 2 Somme des entiers de 1 à n

Exercice 3 Puissance : combien d'appels, quelle valeur ?

Exercice 4 Somme des chiffres d'un entier

Exercice 5 Le PGCD par l'algorithme d'Euclide

Exercice 6 Maximum d'une liste

Exercice 7 Fibonacci : compter les appels

Exercice 8 Compter les déplacements d'un programme récursif

Exercice 9 Réparer une fonction qui ne s'arrête pas

Exercice 10 Palindrome sur une chaîne de caractères

Les questions qu'on se pose

Sources

Primaire

Collège

Lycée

Supérieur