Une introduction rapide à la récursivité en Javascript

La fonction s'appelle elle-même jusqu'à ce que quelqu'un l'arrête.

La récursivité peut sembler difficile pour les nouveaux développeurs. C'est peut-être parce que de nombreuses ressources l'enseignent à l'aide d'exemples algorithmiques (Fibonacci, listes liées). Nous espérons que cet article présentera les choses clairement, en utilisant un exemple simple.

Idée de base

La récursivité est lorsqu'une fonction s'appelle elle-même jusqu'à ce que quelqu'un l'arrête. Si personne ne l'arrête alors il va récursion (lui - même appeler) pour toujours.

Les fonctions récursives vous permettent d'effectuer une unité de travail plusieurs fois. C'est exactement ce que les for/whileboucles nous permettent d'accomplir! Parfois, cependant, les solutions récursives sont une approche plus élégante pour résoudre un problème.

Fonction de compte à rebours

Créons une fonction qui compte à rebours à partir d'un nombre donné. Nous allons l'utiliser comme ça.

countDownFrom(5); // 5 // 4 // 3 // 2 // 1 

Et voici notre algorithme pour résoudre ce problème.

1. Prenez un paramètre appelé number. Ceci est notre point de départ.
2. Allez de numberbas en haut 0, en enregistrant chacun d'eux en cours de route.

Nous allons commencer par une forapproche en boucle, puis la comparer à une approche récursive.

Approche impérative (boucles)

function countDownFrom(number) { for (let i = number; i > 0; i--) { console.log(i); } } countDownFrom(5); // 5 // 4 // 3 // 2 // 1 

Celui-ci contient les deux étapes algorithmiques.

1. ✅ Prenez un paramètre appelé number.
2. ✅ Enregistrez tout de numberà 0.

Approche récursive

function countDownFrom(number) { if (number === 0) { return; } console.log(number); countDownFrom(number - 1); } countDownFrom(5); // 5 // 4 // 3 // 2 // 1 

Celui-ci passe également.

1. ✅ Prenez un paramètre appelé number.
2. ✅ Enregistrez tout de numberà 0.

Donc, conceptuellement, les deux approches sont les mêmes. Cependant, ils font le travail de différentes manières.

Déboguer notre solution impérative

Pour un exemple plus visuel, mettons une debuggerversion dans notre boucle et jetons-la dans les outils de développement Chrome.

function countDownFrom(number) { for (let i = number; i > 0; i--) { console.log(i); debugger; } } 

Voyez comment il utilise une variable supplémentaire,, ipour suivre le nombre actuel? Au fur et à mesure que vous itérez, idiminue, finissant par atteindre 0et terminer.

Et dans la forboucle, nous avons spécifié "stop if i > 0".

Débogage de notre solution récursive

function countDownFrom(number) { if (number === 0) { return; } console.log(number); debugger; countDownFrom(number - 1); } 

La version récursive n'a pas besoin de variables supplémentaires pour suivre sa progression. Remarquez comment la pile de fonctions ( pile d'appels ) augmente à mesure que nous récurons?

C'est parce que chaque appel à countDownFromajoute à la pile, l'alimentant number - 1. En faisant cela, nous transmettons une mise à jour à numberchaque fois. Aucun état supplémentaire nécessaire!

C'est la principale différence entre les deux approches.

1. Iterative utilise l'état interne (variables supplémentaires pour le comptage, etc.).
2. Récursif ne le fait pas, il transmet simplement des paramètres mis à jour entre chaque appel.

Mais comment l'une ou l'autre des versions sait-elle quand s'arrêter?

Boucles infinies

Au cours de vos voyages, vous avez peut-être été averti de la redoutable boucle infinie.

? THIS RUNS FOREVER, BE WARNED ? while (true) { console.log('WHY DID YOU RUN THIS?!' } ? THIS RUNS FOREVER, BE WARNED ? for (i = 0;;) { console.log('WHY DID YOU RUN THIS?!') } 

Puisqu'ils fonctionneraient théoriquement pour toujours, une boucle infinie arrêtera votre programme et plantera éventuellement votre navigateur. Vous pouvez les éviter en codant toujours une condition d'arrêt .

✅ This does not run forever x = 0; while (x < 3) { console.log(x); x++; } ✅ This does not run forever for (x = 0; x < 3; x++) { console.log(x); } 

Dans les deux cas, nous enregistrons x, incrémentons et nous arrêtons quand cela devient 3. Notre countDownFromfonction avait une logique similaire.

// Stop at 0 for (let i = number; i > 0; i--) 

Encore une fois, les boucles ont besoin d'un état supplémentaire pour déterminer quand elles doivent s'arrêter. C'est pour ça xet ipour ça .

Récursivité infinie

La récursion présente également le même danger. Il n'est pas difficile d'écrire une fonction d'auto-référencement qui plantera votre navigateur.

?THIS RUNS FOREVER, BE WARNED? function run() { console.log('running'); run(); } run(); // running // running // ... 

Without a stopping condition, run will forever call itself. You can fix that with an if statement.

✅ This does not run forever function run(x) { if (x === 3) return; console.log('running'); run(x + 1); } run(0); // running // running // running // x is 3 now, we're done. 

Base case

This is known as the base case–our recursive countDownFrom had one.

if (number === 0) { return; } 

It's the same idea as our loop's stopping logic. Whichever approach you pick, always remember that at some point it needs to be stopped.

Summary

• Recursion is when a function calls itself until someone stops it.
• It can be used instead of a loop.
• If no one stops it, it'll recurse forever and crash your program.
• A base case is a condition that stops the recursion. Don't forget to add them!
• Loops use extra state variables for tracking and counting, while recursion only uses the provided parameters.

Thanks for reading

Pour plus de contenu comme celui-ci, consultez //yazeedb.com. Et faites-moi savoir ce que vous aimeriez voir d'autre! Mes DM sont ouverts sur Twitter.

Jusqu'à la prochaine fois!