Recursion dans JavaScript fonctionnel

Vous avez peut-être entendu parler de fonctions récursives en JavaScript, et même essayé d'en écrire. Mais vous n'avez peut-être pas vu de nombreux exemples de récursivité qui fonctionne réellement. En fait, outre la particularité de cette approche, vous n'avez peut-être pas considéré quand et où la récursivité est utile, ou à quel point elle est dangereuse si elle est utilisée mal.

Points clés

• Recursion est une méthode JavaScript qui permet à la fonction de s'appeler à plusieurs reprises jusqu'à ce que le résultat soit atteint. Il est particulièrement utile pour les problèmes impliquant des branches itératives, telles que les mathématiques fractales, le tri ou la traversée des structures de données complexes ou non linéaires.
• Bien que la récursivité puisse rendre le code plus concis et plus facile à comprendre, s'il est utilisé mal, il peut être dangereux en raison du risque de dépasser la capacité de mémoire du moteur. En effet, les fonctions récursives JavaScript doivent garder une trace d'où elles sont appelées à chaque fois afin qu'ils puissent continuer à s'exécuter au bon endroit.
• Dans de nombreux langages de programmation fonctionnelle, une technique appelée optimisation des appels de queue est utilisée pour gérer la récursivité. Cela permet à chaque boucle continue de la fonction récursive de se produire immédiatement, plutôt que de l'empilement en mémoire. Cependant, la plupart des compilateurs JavaScript ne sont pas encore optimisés pour cela.
• Les fonctions de rebond personnalisées peuvent être construites pour gérer itérativement l'exécution récursive, ne laissant qu'une seule opération sur la pile à la fois. Cela peut aider à éviter de créer des opérations de pile profonde en attendant d'être effectuées, mais généralement au détriment des performances et de la lisibilité.

Objectif de la récursivité

La récursivité est une technique qui itère à travers l'opération en ayant une fonction s'appeler à plusieurs reprises jusqu'à ce que le résultat soit obtenu. La plupart des boucles peuvent être réécrites dans des styles récursifs, et dans certains langages de programmation fonctionnelle, cette méthode de boucle est la valeur par défaut.

Cependant, bien que le style de programmation fonctionnelle de JavaScript prend en charge les fonctions récursives, nous devons réaliser que la plupart des compilateurs JavaScript ne sont pas actuellement optimisés en toute sécurité pour eux.

La récursivité est mieux utilisée lorsque vous devez appeler à plusieurs reprises la même fonction avec différents paramètres dans la boucle. Bien qu'il puisse être utilisé dans de nombreux cas, il est plus efficace pour résoudre des problèmes impliquant des branches itératives telles que les mathématiques fractales, le tri ou la traversée des nœuds de structures de données complexes ou non linéaires.

L'une des raisons pour lesquelles la récursivité est privilégiée dans les langages de programmation fonctionnelle est qu'il permet un code de construction qui ne nécessite pas l'utilisation de variables locales pour définir et maintenir l'état. Les fonctions récursives sont également faciles à tester car elles sont faciles à écrire de manière pure, ont une valeur de retour spécifique et cohérente pour une entrée donnée et n'ont aucun effet secondaire sur l'état de la variable externe.

cycle

Un exemple de fonction classique que la récursivité peut être appliquée est factorielle. Il s'agit d'une fonction qui renvoie le résultat d'un nombre multiplié à plusieurs reprises par chaque entier précédent, jusqu'à 1.

Par exemple, le factoriel de 3 est:

<code>3 × 2 × 1 = 6</code>

Le factoriel de

6 est:

<code>3 × 2 × 1 = 6</code>

Vous pouvez voir à quelle vitesse ces résultats augmentent. Vous pouvez également nous voir répéter le même comportement encore et encore. Nous prenons le résultat d'une opération de multiplication et le multiplions par la deuxième valeur à moins 1. Ensuite, nous le faisons encore et encore jusqu'à ce que nous atteignions 1.

En utilisant une boucle pour une boucle, il n'est pas difficile de créer une fonction qui itère pour le faire jusqu'à ce que le bon résultat soit renvoyé:

<code>6 × 5 × 4 × 3 × 2 × 1 = 720</code>

Cela fonctionne, mais du point de vue de la programmation fonctionnelle, il n'est pas élégant. Pour prendre en charge la boucle FOR, puis renvoyer le résultat, nous devons utiliser plusieurs variables locales qui maintiennent et suivent l'état. Ne serait-il pas plus concis si nous pouvions jeter la boucle pour et adopter une méthode JavaScript plus fonctionnelle?

Recursion

Nous savons que JavaScript nous permet d'écrire des fonctions qui prennent des fonctions comme des paramètres. Et si nous voulons utiliser la fonction réelle que nous écrivons et l'exécutons dans le contexte où nous l'exécutons?

Est-ce même possible? bien sûr! Par exemple, considérez une boucle aussi simple:

var factor = function(number) {
  var result = 1;
  var count;
  for (count = number; count > 1; count--) {
    result *= count;
  }
  return result;
};
console.log(factor(6));
// 720

Une fois cela fait, la valeur du compteur a changé, mais la boucle a terminé son travail d'impression de chaque valeur, car nous en avons lentement extrait l'état.

Les versions récursives de la même boucle peuvent ressembler davantage à ceci:

var counter = 10;
while(counter > 0) {
    console.log(counter--);
}

Avez-vous vu comment nous appelons la fonction de compte à rebours directement dans la définition de la fonction à rebours? JavaScript le gère comme un boss et fait seulement ce que vous voulez qu'il fasse. Chaque fois que le compte à rebours est exécuté, JavaScript suit où il est appelé, puis remonte à la pile de cet appel de fonction jusqu'à ce qu'il soit terminé. Notre fonction évite également la modification de l'état de toute variable, mais utilise toujours les valeurs passées pour contrôler la récursivité.

Retour à notre cas factoriel, nous pouvons réécrire la fonction précédente comme celle-ci pour utiliser la récursivité:

var countdown = function(value) {
    if (value > 0) {
        console.log(value);
        return countdown(value - 1);
    } else {
        return value;
    }
};
countdown(10);

L'écriture de code de cette manière nous permet de décrire l'intégralité du processus de manière apatride sans aucun effet secondaire. Il convient également de noter que nous testons d'abord les valeurs des paramètres transmises à la fonction, puis effectuons des calculs. Nous voulons toute fonction qui est sur le point de s'appeler pour sortir rapidement et proprement lorsqu'elle atteint sa terminaison. Pour les factoriels calculés de cette manière, lorsque le nombre entrant est nul ou négatif, la situation de terminaison est atteinte (nous pouvons également tester des valeurs négatives et renvoyer différents messages si nous le souhaitons).

Optimisation des appels de queue

L'un des problèmes des implémentations contemporaines JavaScript est qu'ils n'ont pas de moyen standard d'empêcher les fonctions récursives de s'accumuler infiniment et de consommer de la mémoire jusqu'à ce qu'ils dépassent la capacité du moteur. Les fonctions récursives JavaScript doivent garder une trace d'où elles sont appelées à chaque fois afin qu'ils puissent continuer à s'exécuter au bon endroit.

Dans de nombreux langages de programmation fonctionnelle tels que Haskell et Scheme, il est géré à l'aide d'une technique appelée optimisation des appels de queue. En utilisant l'optimisation des appels de queue, chaque boucle continue dans la fonction récursive se produira immédiatement, plutôt que de l'empilement en mémoire.

En théorie, l'optimisation des appels de queue fait partie de la norme ECMAScript 6 (la prochaine version de JavaScript actuelle), mais la plupart des plateformes ne l'ont pas encore entièrement implémentée.

Fonction de rebond

Si nécessaire, il existe des moyens de forcer JavaScript à exécuter des fonctions récursives de manière sûre. Par exemple, des fonctions de rebond personnalisées peuvent être conçues pour gérer itérativement l'exécution récursive, ne laissant qu'une seule opération sur la pile à la fois. La fonction de rebond utilisée de cette manière peut profiter de la capacité de JavaScript à lier les fonctions à un contexte spécifique afin de rebondir la fonction récursive à elle-même, en construisant le résultat un à la fois jusqu'à ce que la boucle soit terminée. Cela évitera de créer des opérations de pile profonde en attendant l'exécution.

En fait, l'utilisation d'une fonction de rebond réduit souvent les performances pour la sécurité. De plus, la plupart de l'élégance et de la lisibilité que nous obtenons en écrivant des fonctions récursivement est perdue dans la convolution du code nécessaire pour que cette approche fonctionne en JavaScript.

Si vous êtes curieux, je vous encourage à en savoir plus sur ce concept et à partager vos pensées dans la discussion ci-dessous. Vous pouvez commencer par un court sujet sur Stackoverflow et explorer certains articles de Don Taylor et Mark McDonnell qui approfondissent les avantages et les inconvénients des fonctions de rebond en JavaScript.

Nous ne sommes pas encore à ce moment-là

La récursivité est une technique puissante qui mérite d'être connue. Dans de nombreux cas, la récursivité est le moyen le plus simple de résoudre des problèmes complexes. Cependant, avant que Ecmascript 6 ne s'implémente entièrement avec l'optimisation des appels de queue où nous en avons besoin, nous devons faire très attention à la façon et à la façon dont le récursif est appliqué.

FAQ sur la récursivité dans JavaScript fonctionnel (FAQ)

Quelle est la situation de base dans la récursivité? Pourquoi est-ce important?

La situation de base dans la récursivité est la condition qui empêche la fonction de s'appeler infiniment. Il est crucial car sans lui, la fonction récursive s'appellera infiniment, provoquant une erreur de débordement de pile. La situation de base est généralement la condition qu'une fonction vérifie avant de passer un appel récursif. Si cette condition est remplie, la fonction renvoie une valeur et cesse de s'appeler.

Comment fonctionne la récursion en JavaScript?

Dans JavaScript, Recursion fonctionne en appelant la fonction elle-même jusqu'à ce que la situation de base soit atteinte. La fonction est divisée en cas de base et cas récursif. Le cas de base renvoie une valeur sans appeler à nouveau la fonction, tandis que le cas récursif appelle à nouveau la fonction avec différents paramètres. La fonction continue de s'appeler jusqu'à ce que le boîtier de base soit atteint, à quel point il commence à renvoyer la valeur.

Qu'est-ce que la récursion de la queue en javascript?

La récursivité de la queue est un type spécial de récursivité, où l'appel récursif est la dernière opération de la fonction. Ceci est important car il permet à l'optimisation du moteur JavaScript de se concrétiser, en utilisant une technique appelée optimisation des appels de queue. Cela peut réduire considérablement la quantité de mémoire utilisée par la fonction, ce qui lui permet de gérer des entrées plus grandes.

Quels sont les avantages et les inconvénients de l'utilisation de la récursivité en JavaScript?

La récursivité peut rendre le code plus concis et facile à comprendre en divisant des problèmes complexes en problèmes plus simples. Il est particulièrement utile pour les tâches telles que la traversée des structures de données d'arbres. Cependant, la récursivité peut également être moins efficace que les solutions itératives, et si elle est implémentée de manière incorrecte, elle peut entraîner une erreur de débordement de pile.

Comment éviter les erreurs de débordement de pile dans les fonctions récursives?

Lorsque la fonction récursive s'appelle trop de fois et remplit la pile d'appels, une erreur de débordement de pile se produira. Pour éviter cela, assurez-vous que votre fonction récursive a le cas de base qui finira par arriver. Envisagez également d'utiliser la récursivité de la queue, que le moteur JavaScript peut optimiser pour utiliser moins de mémoire.

Comment la récursivité est-elle utilisée dans la programmation fonctionnelle?

Dans la programmation fonctionnelle, la récursivité est souvent utilisée comme remplacement des boucles. Étant donné que la programmation fonctionnelle décourage l'utilisation des états variables, la récursivité peut être utilisée pour effectuer des opérations répétées sans modifier aucun état.

Toutes les fonctions récursives peuvent-elles être converties en fonctions itératives?

Oui, en théorie, toutes les fonctions récursives peuvent être converties en fonctions itératives. Cependant, les versions itératives peuvent être plus complexes et difficiles à comprendre, en particulier pour les fonctions impliquant des traversées complexes d'arbres ou de graphiques.

Qu'est-ce que la récursion mutuelle en JavaScript?

La récursivité mutuelle fait référence à deux fonctions ou plus qui sont appelées les unes avec les autres dans une boucle. Cela peut être une technique puissante pour résoudre certains types de problèmes, mais il peut également être plus difficile de comprendre et de déboguer qu'une simple récursivité.

Comment déboguer les fonctions récursives dans JavaScript?

Les fonctions récursives de drainage peuvent être difficiles en raison des appels de fonction répétés. Cependant, il peut être utile d'imprimer les paramètres de la fonction et les valeurs de retour à chaque étape à l'aide de l'instruction Console.log. De plus, il est très utile d'utiliser un outil de débogueur qui vous permet d'effectuer des appels de fonction étape par étape.

Y a-t-il des considérations de performances lors de l'utilisation de la récursivité?

Oui, une fonction récursive peut ne pas être aussi efficace que son homologue itératif en raison de la surcharge des appels de fonction répétés. S'ils s'appellent trop de fois, ils peuvent également provoquer une erreur de débordement de pile. Cependant, dans de nombreux cas, la lisibilité et la simplicité d'une solution récursive peuvent l'emporter sur ces considérations de performance.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!