Une fonction qui s'appelle elle-mĂŞme
Utilisez les flèches, cliquez ou glissez pour naviguer
1. Comprendre la récursion
Une fonction qui s'appelle elle-mĂŞme
2. Identifier cas de base et cas récursif
Quand s'arrĂŞter et comment avancer
3. Implémenter des fonctions récursives
Factorielle, Fibonacci, somme de tableau
4. Visualiser la pile d'appels
Comprendre l'empilement et le dépilage
La récursion en une phrase
Une fonction qui s'appelle elle-mĂŞme
Les deux ingrédients
Cas de base (STOP) et cas récursif (AVANCER)
Exemple classique : la factorielle
5! = 5 Ă— 4 Ă— 3 Ă— 2 Ă— 1
La pile d'appels (call stack)
Visualiser l'empilement et le dépilage
Autres exemples
Fibonacci, somme d'un tableau, compte Ă rebours
Une fonction qui s'appelle elle-mĂŞme
Comme des miroirs face à face qui se reflètent à l'infini
🛑
Quand s'arrĂŞter ?
La condition qui stoppe la récursion
➡️
Comment avancer ?
L'appel qui rapproche du cas de base
⚠️ Sans cas de base = boucle infinie = Stack Overflow!
Chaque poupée contient une poupée plus petite
La plus petite (cas de base) ne contient rien — on s'arrête là !
// Sans cas de base...
function boucleInfinie() {
return boucleInfinie();
}
Maximum call stack size exceeded
La pile déborde car chaque appel reste en mémoire!
5! = 5 Ă— 4 Ă— 3 Ă— 2 Ă— 1 = 120
n! = n Ă— (n-1) Ă— (n-2) Ă— ... Ă— 1
Donc : n! = n Ă— (n-1)!
FONCTION factorielle(n)
SI n = 0 ALORS
RETOURNER 1 // Cas de base
SINON
RETOURNER n × factorielle(n - 1) // Cas récursif
FIN SI
FIN FONCTION
🛑 Cas de base
n = 0 → retourne 1
➡️ Cas récursif
n Ă— factorielle(n-1)
function factorielle(n) {
// Cas de base : 0! = 1
if (n === 0) {
return 1;
}
// Cas récursif : n! = n × (n-1)!
return n * factorielle(n - 1);
}
factorielle(5) retourne 120
Appel de factorielle(5)
Chaque appel est "empilé" en mémoire
Les résultats "remontent" depuis le cas de base
RĂ©sultat final : 120
Sans cas de base
function fact(n) {
return n * fact(n-1);
}
// Boucle infinie! ❌
Avec cas de base
function fact(n) {
if (n === 0) return 1;
return n * fact(n-1);
}
// Correct! âś…
đź’ˇ TOUJOURS commencer par Ă©crire le cas de base!
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Chaque nombre est la somme des deux précédents
fib(n) = fib(n-1) + fib(n-2)
FONCTION fibonacci(n)
SI n ≤ 1 ALORS
RETOURNER n // Cas de base: fib(0)=0, fib(1)=1
SINON
RETOURNER fibonacci(n-1) + fibonacci(n-2)
FIN SI
FIN FONCTION
🛑 Cas de base
n ≤ 1 → retourne n
fib(0) = 0, fib(1) = 1
➡️ Cas récursif
fib(n-1) + fib(n-2)
Deux appels récursifs!
function fibonacci(n) {
// Cas de base
if (n <= 1) {
return n;
}
// Cas récursif
return fibonacci(n - 1) + fibonacci(n - 2);
}
fibonacci(6) retourne 8
Pour fib(5), on calcule plusieurs fois les mĂŞmes valeurs!
fib(5)
├── fib(4)
├── fib(3)
├── fib(2) → calculé 2x
└── fib(2) → calculé 3x!
└── fib(3) → calculé 2x
La version naïve est très inefficace
Pour n=50, cela prendrait des années!
Version itérative (recommandée)
function fibIter(n) {
let a = 0, b = 1;
for (let i = 0; i < n; i++) {
[a, b] = [b, a + b];
}
return a;
}
// O(n) - efficace! âś…
Ou mémoïsation (cache)
const memo = {};
function fibMemo(n) {
if (n in memo) return memo[n];
if (n <= 1) return n;
memo[n] = fibMemo(n-1) + fibMemo(n-2);
return memo[n];
}
// O(n) avec cache âś…
💡 La récursion est élégante mais pas toujours efficace!
[1, 2, 3, 4, 5] → 15
Somme = premier élément + somme du reste
FONCTION somme(tableau)
SI tableau est vide ALORS
RETOURNER 0 // Cas de base
SINON
RETOURNER tableau[0] + somme(reste du tableau)
FIN SI
FIN FONCTION
🛑 Cas de base
Tableau vide → retourne 0
➡️ Cas récursif
premier + somme(reste)
function somme(arr) {
// Cas de base : tableau vide
if (arr.length === 0) {
return 0;
}
// Cas récursif
return arr[0] + somme(arr.slice(1));
}
somme([1, 2, 3, 4, 5]) retourne 15
RĂ©sultat : 1+2+3+4+5+0 = 15
5 → 4 → 3 → 2 → 1 → Décollage!
Un exemple où l'action se fait avant l'appel récursif
function countdown(n) {
// Cas de base
if (n <= 0) {
console.log("DĂ©collage!");
return;
}
// Action AVANT l'appel récursif
console.log(n);
countdown(n - 1);
}
countdown(5) affiche : 5, 4, 3, 2, 1, DĂ©collage!
Erreur classique
function infinite() {
return infinite(); // Pas de cas de base!
}
RangeError: Maximum call stack size exceeded
La pile d'appels déborde après ~10 000 appels
❌ Mauvais : n'avance pas
function bad(n) {
if (n === 0) return 1;
return bad(n); // n ne change pas!
}
âś… Bon : avance vers le cas de base
function good(n) {
if (n === 0) return 1;
return n * good(n - 1); // n-1
}
đź’ˇ Chaque appel doit rapprocher du cas de base
TOUJOURS commencer par le cas de base
Écrivez-le en premier, avant tout le reste
Dessinez la pile d'appels
Visualiser aide énormément à comprendre
VĂ©rifiez que chaque appel rapproche du cas de base
n-1, slice(1), etc. — il faut progresser
Pratiquez avec des exemples simples
Factorielle, compte à rebours, somme — puis passez aux complexes
Les 2 ingrédients
La pile d'appels
Exemples classiques
Attention!
La récursion : élégante, mais à utiliser avec prudence!