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

La récursivité en NSI : cours de Terminale

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

L'essentiel

Une fonction est récursive quand elle s'appelle elle-même ; elle se ramène à un problème plus petit du même type.³
Il faut toujours un cas de base (condition d'arrêt) sans appel récursif, sinon le programme ne se termine pas.¹
Chaque appel récursif doit rapprocher des cas de base : c'est l'argument de terminaison.
Les structures comme les listes et les arbres se définissent et se traitent naturellement de façon récursive.³
Un programme récursif peut être plus lent que sa version itérative ; on choisit selon la clarté et le coût.¹

Introduction : une fonction qui s'appelle elle-même

Jusqu'ici, pour répéter une opération, tu as utilisé des boucles for et while. Il existe une autre manière de répéter : écrire une fonction qui s'appelle elle-même. C'est la récursivité, un chapitre du thème « Langages et programmation » de la spécialité NSI, que tu abordes après la calculabilité et la décidabilité.

Côté vocabulaire, le terme dérive de l'anglais recursive, lui-même tiré du latin recurrere, « revenir en arrière ».⁴ L'idée dépasse largement l'informatique : une démarche est récursive quand elle se décrit en se référant à elle-même, ce qui revient à appliquer plusieurs fois la même règle.³

En informatique, une fonction (ou, plus généralement, un algorithme) qui s'appelle elle-même au cours de son exécution est dite récursive.³ On s'en sert surtout pour parcourir des structures de données récursives, et pour mettre en œuvre la méthode « diviser pour régner ».³

Dans ce cours, tu vas :

comprendre le fonctionnement d'un appel récursif, pas à pas ;
apprendre à concevoir une fonction récursive à partir d'un cas de base et d'un cas récursif ;
justifier qu'une fonction récursive se termine ;
visualiser la pile des appels et comprendre ses limites ;
écrire des fonctions récursives sur des nombres, des listes et des chaînes ;
comparer récursivité et itération, ce qui revient régulièrement à l'épreuve.

Pour la suite, le chapitre prépare les notions de modularité, de paradigmes de programmation et de mise au point des programmes.

Premier exemple : la factorielle

Prenons le calcul de la factorielle d'un entier $n \geq 0$ , notée $n!$ . On la définit par $0! = 1$ et, pour $n \geq 1$ , $n! = n \times (n-1)!$ . Cette définition est déjà récursive : pour calculer $n!$ , on a besoin de $(n-1)!$ , qui est un problème du même genre, mais plus petit.

ExempleLa fonction factorielle en Python

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

Le test n == 0 traite le cas le plus simple. Dans tous les autres cas, la fonction se rappelle avec un argument plus petit d'une unité.

Déroulons factorielle(3). Chaque ligne décrit ce que la fonction attend :

factorielle(3) renvoie 3 * factorielle(2) : il faut d'abord connaître factorielle(2) ;
factorielle(2) renvoie 2 * factorielle(1) ;
factorielle(1) renvoie 1 * factorielle(0) ;
factorielle(0) renvoie 1 directement : plus aucun appel.

La « descente » s'arrête là. Commence alors la « remontée » : factorielle(1) vaut $1 \times 1 = 1$ , puis factorielle(2) vaut $2 \times 1 = 2$ , enfin factorielle(3) vaut $3 \times 2 = 6$ .

Retiens ce mouvement en deux temps : on descend en empilant des calculs en attente, puis on remonte en les terminant un à un.

Appel de 33 * factorielle(2) est mis en attente
Descentefactorielle(2), puis factorielle(1) attendent
Cas de basefactorielle(0) renvoie 1 sans autre appel
Remontée1, puis 2, puis 6 : le résultat final

Déroulement de factorielle(3) · On descend en empilant les calculs, puis on remonte en les terminant.

Anatomie d'une fonction récursive

Terminaison : pourquoi la fonction s'arrête

Écrire une fonction récursive ne suffit pas : il faut être sûr qu'elle se termine pour toute donnée autorisée. En NSI, on le justifie avec un variant, une grandeur entière positive ou nulle qui diminue strictement à chaque appel récursif.

Prenons factorielle(n) avec $n \geq 0$ entier. Le variant est $n$ lui-même :

$n$ est un entier positif ou nul ;
à chaque appel récursif, on passe de $n$ à $n - 1$ , donc la valeur diminue strictement ;
un entier positif ou nul ne peut pas diminuer strictement indéfiniment : on finit donc par atteindre $0$ , qui est le cas de base.

ExempleUn cas où la terminaison échoue

def compte_a_rebours(n):
    if n == 0:
        return 0
    return compte_a_rebours(n - 2)

Appelée avec n = 5, cette fonction passe par $5, 3, 1, -1, -3, \dots$ et ne tombe jamais sur 0 : le variant devient négatif et la condition d'arrêt n'est jamais atteinte. Appelée avec n = 4, elle s'arrête. Une fonction qui ne se termine que pour certaines données est donc fausse : corrige-la avec if n <= 0 ou en traitant aussi le cas n == 1.

La pile d'appels : ce qui se passe en mémoire

Pendant que factorielle(2) attend le résultat de factorielle(1), elle n'est pas terminée : il faut garder en mémoire la valeur de son n et l'endroit où reprendre le calcul. L'interpréteur range ces informations dans une pile d'appels. À chaque appel, un nouveau « cadre » est empilé ; quand un appel renvoie sa valeur, son cadre est dépilé.

ExempleÉtat de la pile pour factorielle(3)

Au plus profond, la pile contient, du bas vers le haut :

Cadre	Valeur de `n`	Calcul en attente
1 (premier appel)	3	`3 * ...`
2	2	`2 * ...`
3	1	`1 * ...`
4 (sommet)	0	renvoie `1`

Quand le cadre 4 renvoie 1, il est dépilé et le cadre 3 peut calculer 1 * 1, et ainsi de suite jusqu'au cadre 1.

Récursivité sur les listes et les chaînes

Le document d'accompagnement d'Éduscol propose des exemples de programmes récursifs sur les chaînes de caractères, et un exercice sur la recherche du maximum d'une liste.¹ Les structures de données elles-mêmes peuvent être récursives : un arbre binaire, par exemple, est soit vide, soit constitué d'un nœud qui porte deux arbres binaires de taille inférieure.³ Une liste se prête au même raisonnement : une liste est soit vide, soit un élément suivi d'une liste plus courte.

ExempleSomme des éléments d'une liste

def somme(L):
    if len(L) == 0:
        return 0
    return L[0] + somme(L[1:])

Pour somme([4, 1, 7]) :

4 + somme([1, 7])
4 + (1 + somme([7]))
4 + (1 + (7 + somme([])))
somme([]) renvoie 0, donc le total est $4 + 1 + 7 + 0 = 12$ .

ExempleLongueur d'une chaîne, sans utiliser len

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

Le cas de base est la chaîne vide ; sinon on compte le premier caractère et on s'appelle sur le reste. Pour "nsi", on obtient $1 + 1 + 1 + 0 = 3$ .

ExempleRecherche du maximum d'une liste non vide

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

Ici le cas de base est la liste à un seul élément : le maximum d'une liste vide n'existe pas, donc on ne descend pas jusqu'à la liste vide. Pour [3, 9, 2], on calcule maximum([9, 2]), qui vaut 9, puis on compare 3 et 9 : le résultat est 9.

Plusieurs appels récursifs : l'exemple de Fibonacci

La suite de Fibonacci est définie par $F_0 = 0$ , $F_1 = 1$ et, pour $n \geq 2$ , $F_n = F_{n-1} + F_{n-2}$ . Les deux premiers termes sont les cas de base, ce qui correspond aux instructions fib(1) et fib(0) du programme récursif.¹ Le sujet fait partie des activités que l'on demande aux élèves : programmer la fonction fib de façon récursive.¹

ExempleLa fonction fib

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

Pour fib(4) :

fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1)
fib(2) = fib(1) + fib(0) = 1 + 0 = 1
donc fib(3) = 1 + 1 = 2, puis fib(4) = 2 + 1 = 3.

Premières valeurs de la suite de Fibonacci
n	0	1	2	3	4	5	6	7
fib(n)	0	1	1	2	3	5	8	13

Premières valeurs de la suite de Fibonacci

Observe que fib(2) est calculé deux fois dans l'exemple de fib(4). Pour de grandes valeurs de n, les mêmes calculs sont refaits un très grand nombre de fois : le temps d'exécution explose. Ce phénomène illustre que le programme récursif peut être beaucoup plus lent que son équivalent itératif.¹ On peut pallier ce défaut en mémorisant les résultats déjà calculés (technique de la mémoïsation, par exemple avec un dictionnaire), ou en écrivant une version avec boucle.

ExempleVersion itérative de Fibonacci

def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Le nombre d'opérations est proportionnel à n, et aucune pile d'appels ne grandit.

Diviser pour régner et récursivité croisée

ExempleExponentiation rapide

Pour calculer $x^n$ , on utilise : $x^0 = 1$ ; si $n$ est pair, $x^n = (x^{n/2})^2$ ; si $n$ est impair, $x^n = x \times (x^{(n-1)/2})^2$ .

def puissance(x, n):
    if n == 0:
        return 1
    r = puissance(x, n // 2)
    if n % 2 == 0:
        return r * r
    return x * r * r

À chaque appel, l'exposant est divisé par 2 (division entière) : le variant n décroît très vite, et il suffit d'environ $\log_2 n$ appels au lieu de $n$ multiplications. Pour puissance(2, 10), les exposants successifs sont $10, 5, 2, 1, 0$ .

ExempleParité par récursivité croisée

def est_pair(n):
    if n == 0:
        return True
    return est_impair(n - 1)

def est_impair(n):
    if n == 0:
        return False
    return est_pair(n - 1)

est_pair(2) appelle est_impair(1), qui appelle est_pair(0), qui renvoie True. Le variant n diminue à chaque appel, quelle que soit la fonction appelée.

Récursivité ou boucle ? Comparer les deux approches

Boucles et récursivité ont un point commun : elles permettent toutes deux de répéter un nombre d'étapes qu'on ne connaît pas à l'avance, puisqu'il dépend des données fournies au programme.³ Toute fonction récursive peut s'écrire avec une boucle, et inversement ; mais le résultat n'est pas toujours aussi lisible.

Il faut aussi savoir qu'un programme récursif peut être plus lent que son équivalent itératif.¹

Récursivité et itération
Critère	Récursivité	Boucle
Forme	Appel à soi-même	for ou while
Arrêt	Cas de base	Condition de boucle
Mémoire	Pile d'appels	Quelques variables
Cas d'emploi	Arbres, diviser pour régner	Répétitions simples

Récursivité et itération

Méthode pour l'épreuve du bac

La récursivité fait régulièrement l'objet d'un exercice complet à l'épreuve écrite de spécialité NSI. Dans un sujet proposé par Éduscol, l'épreuve dure 3h30, comporte trois exercices indépendants, et l'un d'eux porte sur la récursivité pour 6 points ; la calculatrice n'est pas autorisée.² Cela représente une part importante de la note, d'où l'intérêt de maîtriser les gestes suivants.

Exercices corrigés

Exercice 1 Compter les appels de factorielle

★☆☆Environ 8 min

On utilise la fonction factorielle du cours :

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

Combien d'appels à factorielle (le premier appel compris) sont effectués quand on exécute factorielle(6) ? Donne aussi la valeur renvoyée.

Indice 1

Les arguments successifs sont 6, 5, 4, ... jusqu'au cas de base.

Indice 2

Compte aussi l'appel où l'argument vaut 0.

Voir la correction pas à pas

Les arguments des appels successifs sont 6, 5, 4, 3, 2, 1, puis 0.
L'appel avec l'argument 0 est le cas de base : il ne déclenche aucun nouvel appel.
Il y a donc 7 appels au total, soit $6 + 1$ .
Pour la valeur : $6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 \times 1 = 720$ .

Pour factorielle(n), il y a $n + 1$ appels : la pile atteint $n + 1$ cadres au plus profond.

Exercice 2 Calculer fib(7) à la main

★★☆Environ 12 min

On considère :

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

Quelle valeur renvoie fib(7) ? Présente les valeurs de fib(0) à fib(7) dans l'ordre.

Indice 1

Calcule les valeurs dans l'ordre croissant plutôt que de dérouler tous les appels.

Indice 2

Chaque valeur est la somme des deux précédentes.

Voir la correction pas à pas

Cas de base : fib(0) = 0 et fib(1) = 1.
fib(2) = fib(1) + fib(0) = 1.
fib(3) = fib(2) + fib(1) = 2 puis fib(4) = fib(3) + fib(2) = 3.
fib(5) = 3 + 2 = 5 et fib(6) = 5 + 3 = 8.
fib(7) = fib(6) + fib(5) = 8 + 5 = 13.

Calculer dans l'ordre croissant revient à écrire la version itérative : on ne refait aucun calcul, contrairement au programme récursif.

Exercice 3 Somme des chiffres d'un entier

★★☆Environ 15 min

On souhaite écrire une fonction récursive somme_chiffres(n) qui renvoie la somme des chiffres d'un entier $n \geq 0$ écrit en base 10. On rappelle que n % 10 est le dernier chiffre et n // 10 est l'entier privé de son dernier chiffre.

Écris la fonction.
Justifie sa terminaison.
Calcule somme_chiffres(4825).

Indice 1

Le cas de base est atteint quand il n'y a plus de chiffre : n vaut 0.

Indice 2

Le variant peut être n lui-même.

Voir la correction pas à pas

Cas de base : si n == 0, on renvoie 0.
Cas récursif : on renvoie n % 10 + somme_chiffres(n // 10).
Code : def somme_chiffres(n): / if n == 0: return 0 / return n % 10 + somme_chiffres(n // 10).
Terminaison : le variant n est un entier positif ou nul ; n // 10 est strictement plus petit que n dès que $n \geq 1$ ; on atteint donc 0.
Calcul : $4825 \to 5 + S(482) \to 5 + 2 + S(48) \to 5 + 2 + 8 + S(4) \to 5 + 2 + 8 + 4 + S(0) = 19$ .

La somme des chiffres de 4825 est 19. Le même schéma (dernier élément traité, puis reste) fonctionne pour beaucoup de fonctions sur les entiers.

Exercice 4 Corriger une fonction qui ne se termine pas

★★★Environ 15 min

Voici une fonction censée renvoyer la somme $1 + 2 + \dots + n$ :

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

Que se passe-t-il pour somme_jusqua(5) ? Pour somme_jusqua(4) ?
Corrige la fonction.
Quel variant utilises-tu pour justifier la terminaison de ta version ?

Indice 1

Écris les valeurs successives de l'argument pour n = 5.

Indice 2

Le pas de décroissance doit être 1.

Voir la correction pas à pas

Pour n = 5, les arguments sont 5, 3, 1, -1, -3... : le cas de base n == 0 n'est jamais atteint, la fonction ne se termine pas (erreur RecursionError).
Pour n = 4, les arguments sont 4, 2, 0 : la fonction s'arrête, mais elle renvoie $4 + 2 = 6$ au lieu de $1 + 2 + 3 + 4 = 10$ : le résultat est faux.
Correction : remplacer l'appel par n + somme_jusqua(n - 1).
Variant : n, entier positif ou nul qui diminue de 1 à chaque appel, donc qui atteint 0 (cas de base).

Deux défauts distincts apparaissaient : la non-terminaison pour les entiers impairs et un résultat faux pour les entiers pairs. Vérifier la terminaison et la correction sont deux étapes séparées.

Les questions qu'on se pose

À quoi sert la récursivité, si une boucle peut faire la même chose ?

Toute fonction récursive peut s'écrire avec une boucle, mais la récursivité rend certains codes beaucoup plus courts et proches de la définition mathématique. Elle sert en particulier à traiter les structures de données récursives comme les arbres, et à exprimer le paradigme « diviser pour régner ».³ Elle n'est cependant pas toujours la plus rapide : un programme récursif peut être plus lent que son équivalent itératif.¹

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

Cherche un variant : une quantité entière positive ou nulle qui diminue strictement à chaque appel. Si elle atteint forcément une valeur correspondant au cas de base, la fonction se termine. Vérifie aussi que tous les chemins possibles aboutissent à un cas de base, pas seulement certaines valeurs de l'argument.

Pourquoi Python affiche-t-il « RecursionError : maximum recursion depth exceeded » ?

Chaque appel en attente occupe un cadre dans la pile, et Python limite leur nombre. L'erreur apparaît soit parce que la fonction ne se termine pas (cas de base oublié ou jamais atteint), soit parce que la profondeur nécessaire est simplement trop grande pour la limite fixée. Dans le second cas, une version avec boucle règle le problème.

Qu'est-ce qui tombe à l'épreuve de NSI sur ce chapitre ?

Dans un sujet publié par Éduscol, un exercice entier de 6 points porte sur la récursivité.² On attend typiquement : dérouler un appel à la main, compléter ou écrire une fonction récursive, identifier les cas de base, justifier la terminaison et parfois comparer avec une version itérative.

Faut-il toujours mettre le cas de base en premier ?

Oui, c'est la bonne habitude. Si l'appel récursif est écrit avant de tester le cas de base, il est exécuté même quand il ne le faudrait pas et la fonction ne s'arrête pas. Tester d'abord le cas de base garantit que l'on ne rappelle la fonction que dans le cas général.

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

La récursivité en NSI : cours de Terminale

L'essentiel

Introduction : une fonction qui s'appelle elle-même

Premier exemple : la factorielle

Anatomie d'une fonction récursive

Terminaison : pourquoi la fonction s'arrête

La pile d'appels : ce qui se passe en mémoire

Récursivité sur les listes et les chaînes

Plusieurs appels récursifs : l'exemple de Fibonacci

Diviser pour régner et récursivité croisée

Récursivité ou boucle ? Comparer les deux approches

Méthode pour l'épreuve du bac

Exercices corrigés

Exercice 1 Compter les appels de factorielle

Exercice 2 Calculer fib(7) à la main

Exercice 3 Somme des chiffres d'un entier

Exercice 4 Corriger une fonction qui ne se termine pas

Quiz

Les questions qu'on se pose

Sources

Primaire

Collège

Lycée

Supérieur