NSI · Terminale · Algorithmique
Algorithme récursif
Une fonction qui s’appelle elle-même.
En bref
Un algorithme est récursif quand il résout un problème en s’appelant lui-même sur un cas plus petit.
Un algorithme est récursif quand il résout un problème en s’appelant lui-même sur un cas plus petit. Sa correction repose entièrement sur deux éléments.
Les deux composants obligatoires
| Composant | Ce qu’il garantit | S’il manque |
|---|---|---|
| Le cas de base | Une valeur renvoyée sans rappel | La récursion ne s’arrête jamais |
| L’appel sur un cas strictement plus petit | On se rapproche du cas de base | Le cas de base n’est jamais atteint |
Dans les deux cas : récursion infinie, qui se termine par un dépassement de la pile d’appels.
La pile d’appels
Chaque appel en cours occupe une place en mémoire : ses paramètres et l’endroit où reprendre. Les appels s’empilent, puis se dépilent du plus profond au plus superficiel.
La profondeur est donc limitée : Python la borne par défaut autour de mille appels. Une récursion sur une liste d’un million d’éléments échouera là où une boucle passe sans difficulté.
Écrire une fonction récursive
- Identifier le cas de base et sa valeur ;
- Supposer que la fonction fonctionne déjà pour le cas plus petit — l’acte de foi qui rend la récursivité écrivable ;
- Écrire comment combiner ce résultat avec le cas courant.
Exemples classiques : factorielle, somme d’une liste, puissance, inversion d’une chaîne, tours de Hanoï, parcours d’arbre.
Récursivité et arbres
Les structures récursives par définition — un arbre est un nœud et deux arbres — se traitent naturellement par récursivité.
Un parcours d’arbre écrit en récursif tient en trois lignes ; sa version itérative exige de gérer explicitement une pile.
Le piège de la double récursion
La suite de Fibonacci écrite naïvement rappelle deux fois la fonction à chaque niveau : le nombre d’appels double à chaque rang, le coût devient exponentiel.
Calculer le trentième terme demande plus d’un million d’appels, dont l’immense majorité recalcule ce qui l’a déjà été. La solution — mémoriser — est l’objet de la programmation dynamique.
Récursif ou itératif
| Récursif | Itératif | |
|---|---|---|
| Puissance | Identique | Identique |
| Quand le choisir | Structures récursives, code court | Grande profondeur, performance critique |
La question devant une fonction récursive : « sur quel argument décroît-elle, et jusqu’où ? » Si la réponse n’est pas immédiate, la fonction est fausse.
Teste-toi
6 questions pour vérifier
Touche une réponse : la correction s’affiche tout de suite.
1.Quels sont les deux composants obligatoires d’un algorithme récursif ?
2.Que se passe-t-il en cas de récursion infinie ?
3.Dans quel ordre les appels récursifs se terminent-ils ?
4.Pourquoi une récursion sur un million d’éléments échoue-t-elle en Python ?
5.Pourquoi la version naïve de Fibonacci est-elle si coûteuse ?
6.Toute fonction récursive peut être réécrite de façon itérative.
0 / 6 questions
Dans l’app, ce chapitre a son quiz complet, chronométré, et tes erreurs reviennent au bon moment pour ne plus les refaire.
La fiche de révision, sur une page
Tout « Algorithme récursif » sur une seule page A4 illustrée : l’essentiel, les pièges et un mini-test. Elle se débloque dans l’app avec des gemmes — et ton compte gratuit en offre assez pour tes trois premières fiches.
