💻 Programmation · Fondamentaux
La récursivité
Une fonction récursive s'appelle elle-même sur un problème plus petit, jusqu'à atteindre un cas de base.
function factorielle(n) {
if (n <= 1) return 1; // cas de base
return n * factorielle(n - 1); // appel récursif
}
// factorielle(4) = 4 × 3 × 2 × 1 = 24Les deux ingrédients
- Un cas de base qui arrête la récursion
- Un appel récursif qui se rapproche du cas de base
Sans cas de base, la fonction ne s'arrête jamais.
La pile d'appels
Chaque appel est empilé en mémoire. Trop profond : stack overflow (en JavaScript : RangeError: Maximum call stack size exceeded).
Où c'est naturel
Parcourir des dossiers ou des arbres, diviser pour régner (tri fusion, recherche dichotomique), tours de Hanoï.
Le piège de Fibonacci
Le fib(n-1) + fib(n-2) naïf recalcule les mêmes valeurs : complexité exponentielle. Remède : la mémoïsation (garder les résultats déjà calculés) ou une simple boucle.
Récursif ou itératif ?
Tout algorithme récursif peut s'écrire avec une boucle. Choisis ce qui est le plus lisible.
Récursion = cas de base + problème plus petit à chaque appel.
Pour aller plus loin
Fiche mise à jour le 6 novembre 2026. Une erreur, une précision à proposer ? Écris-nous.