Introduction
La récursivité est un concept puissant en programmation : elle repose sur une fonction qui s'appelle elle-même.
Elle peut sembler un peu délicate à appréhender au début, mais une fois que tu en comprends les fondamentaux, elle devient un outil précieux pour résoudre des problèmes complexes.
Dans ce tutoriel, on va explorer la récursivité en JavaScript à travers des exemples faciles à comprendre.
Qu'est-ce que la récursivité ?
La récursivité intervient quand une fonction s'appelle elle-même, directement ou indirectement.
Cela ressemble à une boucle, mais l'idée est de découper un problème en sous-problèmes plus petits et plus faciles à gérer.
Exemple 1 : le compte à rebours
Commençons par un exemple simple : une fonction de compte à rebours.
function countdown(num) {
// Base case
if (num <= 0) {
console.log('Blastoff!');
return;
}
// Recursive case
console.log(num);
countdown(num - 1);
}
// Call the function
countdown(5);
Dans cet exemple :
-
Cas de base : quand
num devient inférieur ou égal à 0, la fonction affiche « Blastoff! » et arrête de s'appeler.
-
Cas récursif : la fonction affiche la valeur actuelle de
num et s'appelle elle-même avec num - 1.
Exemple 2 : la factorielle
Voyons maintenant un exemple classique de récursivité : le calcul de la factorielle d'un nombre.
function factorial(n) {
// Base case
if (n === 0 || n === 1) {
return 1;
}
// Recursive case
return n * factorial(n - 1);
}
// Test the function
console.log(factorial(5)); // Output: 120
Dans cet exemple :
-
Cas de base : quand
n vaut 0 ou 1, la fonction renvoie 1.
-
Cas récursif : la fonction multiplie
n par la factorielle de n - 1.
Les concepts clés
Le cas de base
Toute fonction récursive doit avoir au moins un cas de base, c'est-à-dire une condition dans laquelle la fonction arrête de s'appeler.
Sans cas de base, la récursivité se poursuivrait indéfiniment, ce qui finit par provoquer un débordement de pile.
Le cas récursif
Le cas récursif définit comment la fonction s'appelle elle-même avec une version plus petite ou plus simple du problème.
Avantages et inconvénients de la récursivité
Avantages :
- Une solution élégante pour certains problèmes.
- Elle imite le concept d'induction mathématique.
Inconvénients :
- Elle peut être moins efficace que les solutions itératives.
- Elle peut provoquer un débordement de pile en cas de récursion profonde.
Conclusion
La récursivité est une technique précieuse qui peut simplifier des problèmes complexes en les découpant en sous-problèmes plus petits et plus faciles à gérer.
Bien comprendre les cas de base et les cas récursifs est essentiel pour écrire des solutions récursives efficaces en JavaScript.
Pour aller plus loin :
Instructions
Tu tiens une pizzeria et tu proposes trois types de pizzas :
- Margherita : 7 $
- Caprese : 9 $
- Formaggio : 10 $
Si les clients le souhaitent, ils peuvent ajouter autant d'options supplémentaires qu'ils veulent : soit "ExtraSauce" pour 1 $, soit "ExtraToppings" pour 2 $.
Ta tâche consiste à écrire du code qui aide le client à déterminer ce que sa commande va lui coûter.
Calcule le prix d'une pizza
Le nom de la pizza est fourni comme premier argument, suivi d'un nombre illimité d'options ; calcule le prix de la pizza en dollars.
pizzaPrice('Margherita');
// => 7
pizzaPrice('Caprese', 'ExtraSauce', 'ExtraToppings');
// => 12
pizzaPrice(
'Caprese',
'ExtraToppings',
'ExtraToppings',
'ExtraToppings',
'ExtraToppings',
);
// => 17
Calcule le prix total d'une commande
Ta fonction est appelée avec une liste de PizzaOrder et doit renvoyer le prix total de la commande en dollars.
Chaque PizzaOrder possède une propriété pizza (le nom de la pizza) et une propriété extras (la liste des options supplémentaires).
const margherita = new PizzaOrder('Margherita');
const caprese = new PizzaOrder('Caprese', 'ExtraToppings');
orderPrice([margherita, caprese]);
// => 18
Tu vas te rendre compte que tu ne peux pas écrire cette fonction de façon récursive, car un test comportant un très grand nombre de commandes déclenchera un Maximum call stack size exceeded.
Pas de panique, c'est voulu : essaie d'implémenter cette fonction avec une boucle impérative !
Tu as de nombreuses possibilités : utiliser reduce, une boucle for, entre autres.
Quand l'interprète JavaScript exécute du code JavaScript, il garde la trace des fonctions dans lesquelles il est entré (qu'il a commencé à appeler) dans une structure de données appelée « pile ».
Quand la fonction renvoie (se termine), elle est retirée de la pile.
Cependant, la taille de cette pile est limitée.
L'erreur la plus fréquente est une fonction récursive qui ne se termine jamais.
Chaque appel est placé sur la pile, mais avant qu'il ne renvoie, un autre appel est placé sur la pile.
function kaboom() {
kaboom()
}
kaboom()
// => RangeError: Maximum call stack size exceeded
La trace de la pile de cette erreur affiche la même ligne encore et encore, ce qui est logique, puisque la fonction s'appelle elle-même.
Bien que cela n'ait pas vraiment d'application pratique dans la plupart des cas, tu peux découvrir jusqu'où cette pile peut monter.
let calls = 0;
function kaboom() {
calls +=1 ;
kaboom()
}
kaboom()
// => RangeError: Maximum call stack size exceeded
console.log(calls)
// => a number, generally higher than 10.000
Il n'existe que deux solutions viables à une erreur de pile d'appels causée par une fonction récursive synchrone :
- faire en sorte que les fonctions renvoient avant que la limite de la pile ne soit atteinte, généralement en ajoutant ou en corrigeant un cas de base.
- réécrire la fonction récursive sous forme de boucle impérative, qui exécutera le corps de la boucle sans avoir à entrer dans une fonction, et donc sans faire grossir la pile.
Exercice d'apprentissage
