Aller au contenu
Ludicademy
Français
Thème Élan
ClairsSombres
S’inscrire
Tle · Algorithmique

La récursivité : un algorithme qui s'appelle lui-même

définir une chose à partir d'elle-même sans tourner en rond

≈ 4 min de lecture · palier Tle · trois questions à la fin

Rédigé avec l’aide d’une IA, relu et corrigé par l’équipe Ludicademy · mis à jour le 20 septembre 2026 · Notre méthode

En bref
  • Un algorithme récursif s'appelle sur un problème strictement plus petit
  • Il lui faut un cas de base, sinon la descente ne s'arrête jamais
  • La descente empile les appels, la remontée calcule les résultats en sens inverse

Se définir soi-même, légalement

Un algorithme RÉCURSIF résout un problème en s'appelant lui-même sur un problème PLUS PETIT. Cela paraît circulaire, et ce ne l'est pas — à deux conditions strictes, faute desquelles le raisonnement tourne effectivement en rond et le programme avec lui.

PREMIÈRE CONDITION : un CAS DE BASE, un cas assez petit pour être résolu sans appel. DEUXIÈME CONDITION : chaque appel doit se faire sur un cas STRICTEMENT plus proche du cas de base. Une définition récursive sans cas de base n'est pas une définition, c'est une boucle infinie déguisée en mathématiques.

Deux définitions du même calcul

La factorielle de nLa version itérativeLa version récursive
Le principeMultiplier de 1 jusqu'à n dans une bouclen fois la factorielle de n moins 1
Le cas de baseLe résultat part à 1factorielle(0) vaut 1, sans appel
Ce qui décroîtLe compteur monte vers nL'argument descend vers 0
Ce qu'on litComment on calculeCE QU'EST le résultat

Dérouler une descente et une remontée

Un appel récursif se déroule en deux temps qu'il faut voir séparément : la DESCENTE empile les appels sans rien calculer, la REMONTÉE calcule les résultats en sens inverse.Calculons factorielle(4). Descente : factorielle(4) a besoin de factorielle(3), qui a besoin de factorielle(2), qui a besoin de factorielle(1), qui a besoin de factorielle(0). Aucun de ces appels n'a encore produit le moindre nombre : ils attendent tous. Cas de base : factorielle(0) vaut 1, et rend enfin quelque chose. Remontée : factorielle(1) vaut 1 fois 1, soit 1. factorielle(2) vaut 2 fois 1, soit 2. factorielle(3) vaut 3 fois 2, soit 6. factorielle(4) vaut 4 fois 6, soit 24. Cinq appels ont coexisté en mémoire au plus profond de la descente — et c'est cette pile, invisible dans le texte du programme, qui explique qu'une récursion trop profonde finisse par déborder.

Récursif ne veut pas dire efficace. La suite de Fibonacci définie récursivement recalcule les mêmes valeurs un nombre exponentiel de fois : fibonacci(50) écrit naïvement demande des milliards d'appels, là où une boucle de cinquante tours suffit. L'élégance d'une définition ne dit rien de son coût.

Quand elle s'impose vraiment

La récursivité gagne là où la structure du problème est elle-même récursive : un arbre dont chaque branche est un arbre, un dossier qui contient des dossiers, le tri fusion qui trie deux moitiés puis les fusionne, les tours de Hanoï où déplacer n disques revient à déplacer n moins 1 disques deux fois. Écrire cela avec des boucles est possible, et pénible : il faut gérer à la main la pile que la récursivité tient toute seule.

OscarDéfinissez-moi « ancêtre ».
SkeletUn ancêtre est un parent, ou un parent d'ancêtre.
OscarVoilà une définition récursive. Où est votre cas de base ?
Skelet« Un parent ». Il ne rappelle rien.
OscarEt qu'est-ce qui décroît à chaque appel ?
SkeletOn remonte d'une génération à chaque fois. Ça finit bien par s'arrêter.
OscarAlors votre définition tient. Elle aurait pu ne pas tenir : « un ancêtre est un ancêtre d'ancêtre » aurait été impeccable et parfaitement vide.
À retenir
  • Un algorithme récursif s'appelle sur un problème strictement plus petit
  • Il lui faut un cas de base, sinon la descente ne s'arrête jamais
  • La descente empile les appels, la remontée calcule les résultats en sens inverse
  • La récursivité s'impose sur les structures récursives, pas partout : elle peut coûter très cher
Exercice

Que manque-t-il à « factorielle(n) vaut n fois factorielle(n moins 1) » ?

Sans valeur donnée sans appel, la descente continue vers les négatifs et ne remonte jamais.

Exercice

Dans le calcul de factorielle(4), quand le premier produit est-il effectué ?

La descente ne fait qu'empiler des appels en attente ; rien ne se calcule avant que le cas de base ne réponde.

Expressions à emporter

Expression Traduction
récursivités'appeler sur un problème plus petit
cas de basele cas résolu sans appel
descente et remontéeempiler d'abord, calculer ensuite

Maintenant, jouez-la

Trois questions pour voir

La règle est lue. Voyons si elle est entrée : trois questions, ici même, sans compte.

7 exercices corrigés de logique en Tle → sans compte, corrigés à chaque réponse

La règle est lue ; il reste à la faire entrer. Trois minutes suffisent.

Jouer « le pont de cordes » → Quiz Express · sans compte

Ou choisissez votre salle :

Et côté jeux de société : 🎪 Échecs → les règles d'échecs

Sur papier : 🖨️ La fiche de cette leçon

Pour réviser : 📝 La fiche de révision et celle du chapitre « algorithmique » (3 leçons)

Toutes les leçons Tle