Sur cette page
Un exemple concret
factorielle(n) renvoie 1 si n = 0 (cas de base), sinon n × factorielle(n − 1). Ainsi factorielle(4) = 4 × 3 × 2 × 1 = 24.
Le piège à éviter
Sans cas de base, ou si l'appel ne s'en rapproche pas, la fonction s'appelle à l'infini et provoque une erreur (dépassement de la pile d'appels).
Pour aller plus loin
Un algorithme récursif résout un problème en le ramenant à une version plus petite du même problème. La structure se retrouve en mathématiques dans les suites définies par récurrence, comme u(n) = 2 × u(n − 1) avec u(0) = 1. Pour que la fonction s'arrête, deux conditions sont indispensables : un cas de base qui renvoie un résultat sans appel récursif, et un paramètre qui se rapproche du cas de base à chaque appel. En pratique, on parle d'un variant, une quantité entière positive qui décroît strictement et garantit la terminaison.
À chaque appel, l'ordinateur empile le contexte dans la pile d'appels. En Python, la profondeur maximale est limitée, par défaut à environ 1 000 appels : au-delà, l'erreur RecursionError est levée. La récursivité n'est pas toujours efficace. Le calcul naïf du nombre de Fibonacci refait de nombreuses fois les mêmes calculs ; pour fib(5), la fonction est appelée 15 fois, et ce nombre croît de façon exponentielle avec n. En revanche, les problèmes diviser pour régner, comme la recherche dichotomique ou le tri fusion, se programment naturellement de façon récursive. Les tours de Hanoï demandent 2ⁿ − 1 déplacements : 7 pour trois disques.
La récursivité figure au programme de NSI en Terminale, dans le thème des algorithmes et de la programmation. Tout programme récursif peut s'écrire avec une boucle, et l'inverse est vrai : le choix dépend de la lisibilité et de l'efficacité. Une version itérative évite de saturer la pile d'appels, tandis qu'une version récursive suit souvent la définition mathématique et se prouve plus facilement. On rencontre aussi la récursivité dans les structures de données, comme les arbres, où un arbre est lui-même constitué de sous-arbres, et dans l'exploration des dossiers d'un disque.
Ne pas confondre
- Boucle (itération) : Elle répète des instructions sans que la fonction s'appelle elle-même. Une version récursive utilise la pile d'appels, une boucle utilise une variable qu'on modifie.
- Appel d'une autre fonction : Une fonction qui en appelle une autre n'est pas récursive. Elle l'est si l'appel désigne la fonction elle-même, directement ou via une autre.
- Raisonnement par récurrence : C'est une méthode de démonstration en mathématiques. La récursivité est une technique de programmation, mais les deux utilisent le même principe d'initialisation puis d'hérédité.
Dans ta copie
Pour calculer la somme des n premiers entiers, j'écris une fonction récursive somme(n). Le cas de base est somme(0), qui renvoie 0. Dans les autres cas, la fonction renvoie n + somme(n − 1). À chaque appel, n diminue d'une unité : c'est le variant, qui garantit qu'on atteindra le cas de base et donc que la fonction se termine. Ainsi, somme(3) = 3 + somme(2) = 3 + 2 + somme(1) = 3 + 2 + 1 + somme(0) = 6. Le raisonnement ressemble à une démonstration par récurrence, où le cas de base joue le rôle de l'initialisation.
À retenir
- Une fonction récursive s'appelle elle-même.
- Un cas de base arrête les appels ; sans lui, la fonction ne se termine pas.
- Chaque appel doit rapprocher le paramètre du cas de base : c'est le variant.
- Python limite la profondeur de récursion, d'où l'erreur RecursionError en cas de dépassement.
Teste-toi
NSI · question corrigée
Qu'est-ce qui est indispensable dans une fonction récursive ?
Voir la réponse
Réponse B. Le cas de base arrête les appels récursifs.
NSI · question corrigée
Soit f définie ainsi : si n = 0, f(n) renvoie 0 ; sinon f(n) renvoie n + f(n − 1). Que renvoie f(3) ?
Voir la réponse
Réponse C. f(3) = 3 + f(2) = 3 + 2 + f(1) = 3 + 2 + 1 + f(0) = 6. La fonction calcule la somme des entiers de 1 à n.
Questions fréquentes
Pourquoi Python affiche-t-il l'erreur RecursionError ?
Parce que la fonction s'appelle trop de fois sans atteindre son cas de base, ou parce que la profondeur dépasse la limite fixée par Python. Il faut alors vérifier que l'appel récursif se rapproche bien du cas de base.
Faut-il toujours préférer la récursivité à une boucle ?
Non. La récursivité est élégante pour les problèmes qui se divisent en sous-problèmes similaires, mais elle consomme de la mémoire. Quand une boucle simple suffit, elle est souvent plus efficace.
Notions liées
Pour réviser tout le chapitre, va sur la page NSI, ou retrouve toutes les définitions dans le lexique du bac. Dans l'application, les quiz reprennent ces notions sur le programme de ta série.