2 minutes
Récursion de base avec des exmples
Dernière mise à jour: 14 septembre, 2022§Commençons Par Une Description
La récursivité peut être simplement expliquée comme une fonction s'appelant à plusieurs reprises jusqu'à ce qu'une condition soit remplie. Elle peut sembler intimidante pour les débutants, mais lorsqu'elle est utilisée correctement, elle est beaucoup plus performante que les itérations.
Étant donné que nous appelons la même fonction encore et encore, nous rendons notre code nettement plus court, plus clair et plus facile à lire et à comprendre.
Nous devons être prudents lorsque nous créons une récursivité, sinon nous pouvons facilement créer une boucle infinie.
Chaque fois que la fonction s'appelle elle-même, une autre pile est créée et tant que la condition n'est pas remplie, la pile ne sera pas supprimée. Cela oblige les récursions à utiliser plus de mémoire. Les valeurs créées dans les piles sont ainsi conservées en mémoire. Jusqu'à ce que la condition de base soit remplie, les piles continuent de s'accumuler. Lorsque la condition de base est remplie, les piles sont effacées de la dernière à la première. Cela signifie que la dernière pile ajoutée est supprimée en premier.
Comme chaque appel récursif crée une pile dans la mémoire, vous, en tant que programmeur, devez faire attention à ne pas provoquer de débordement de pile (stack overflow). Cela peut s'expliquer simplement par le fait que votre programme utilise beaucoup de mémoire par rapport à ce qu'il est censé utiliser. Si vous voulez aller plus loin, consultez [ici](https://www.techtarget.com/whatis/definition/stack-overflow#:~:text=What%20is%20stack%20overflow%3F,been%20allocated% 20à%20cette%20pile.). C'est une des explications simples que j'ai pu trouver.
§Exemples Pratiques
La plus connue et l'une des choses les plus faciles à gérer en utilisant la récursivité est probablement l'algorithme de Fibonacci et la recherche de la factorielle.
function factorial(x) {
// Base Codition
if (x == 0) return 1
else return x * factorial(x - 1);
}
function fibonacci(num) {
// Base Condition
if(num === 1 || num === 0) return num;
else return fibonacci(num-1) + fibonacci(num - 2);
}
Assez utile et concis si vous me demandez.
§Les Avantages et Les Inconvénients
Comme nous pouvons le voir dans les exemples ci-dessus, nous pouvons reproduire la même fonctionnalité en utilisant des itérations. Ils seraient également un peu plus compréhensibles.
Nous devons également tenir compte du fait que jusqu'à ce que le cas de base soit atteint, vos piles continuent de s'accumuler. Cela signifie que vous utiliserez beaucoup plus de mémoire que si vous créiez une itération.
Les parcours d'arbres tels que les algorithmes DFS et BFS reposent sur des solutions récursives. Vous verrez que l'alternative est trop verbeuse et plus difficile à lire et à comprendre.
Si la récursivité était un sujet que vous avez évité jusqu'à présent, voilà ! Vous avez maintenant une compréhension de base du pourquoi et du comment cela fonctionne.
Ilker AkbiyikTable Des Matières
Articles Similaires
