Rédigé avec l’aide d’une IA, relu et corrigé par l’équipe Ludicademy · mis à jour le 20 septembre 2026 · Notre méthode
- 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 n | La version itérative | La version récursive |
|---|---|---|
| Le principe | Multiplier de 1 jusqu'à n dans une boucle | n fois la factorielle de n moins 1 |
| Le cas de base | Le résultat part à 1 | factorielle(0) vaut 1, sans appel |
| Ce qui décroît | Le compteur monte vers n | L'argument descend vers 0 |
| Ce qu'on lit | Comment on calcule | CE 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.

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.







- 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
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.
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.




