Comprendre la récursivité avec JavaScript

Certains problèmes conviennent plus à la récursivité. Par exemple, une séquence telle qu'une séquence de Fibonacci a une définition récursive. Chaque nombre dans la séquence est la somme des deux premiers nombres de la séquence. Les problèmes qui doivent être construits ou traversés avec des structures de données d'arbre peuvent également être résolus par récursivité. Vous vous entraîner à penser récursivement vous donnera de puissantes compétences pour résoudre de tels problèmes.

Dans ce didacticiel, j'expliquerai pas à pas sur le fonctionnement de plusieurs fonctions récursives et vous montrerai certaines techniques pour définir systématiquement les fonctions récursives.

contenu:

• Qu'est-ce que la récursivité?
• Récursivité numérique
• Répertoire
• Construire une liste
• Récursivité de la queue
• Résumer

Qu'est-ce que la récursivité?

Les fonctions définies récursivement sont des fonctions définies par leurs versions simplifiées elles-mêmes. Voici un exemple simplifié:

 fonction doa (n) {
    // ...
    if (n> 0) {
        DOA (N-1);
    }
}

Pour comprendre conceptuellement comment fonctionne la récursivité, nous examinerons un exemple indépendant du code. Supposons que vous soyez responsable de répondre aux appels de l'entreprise. Comme il s'agit d'une entreprise occupée, votre téléphone dispose de plusieurs lignes téléphoniques, vous pouvez gérer plusieurs appels téléphoniques en même temps. Chaque ligne téléphonique a un bouton sur le combiné, qui clignote lorsqu'il y a un appel entrant. Aujourd'hui, lorsque vous allez travailler et allumez le téléphone, quatre lignes clignotent en même temps. Vous commencez donc à répondre à tous les appels.

Vous prenez la première ligne et dites-leur: "Veuillez patienter." Ensuite, vous prenez la deuxième ligne et les mettez également en veille. Ensuite, vous ramassez la troisième ligne et les mettez en veille, etc. Enfin, lorsque vous terminez chaque appel, vous retournez à l'appelant précédent, complétez cet appel et raccrochez.

Chaque appel de cet exemple est similaire à un appel récursif dans une fonction. Lorsque vous recevez un appel, il est mis dans la pile d'appels (en code). Si vous ne pouvez pas effectuer un appel immédiatement, vous le mettez en veille. Si votre appel de fonction ne peut pas être calculé immédiatement, il restera dans la pile d'appels. Lorsque vous pourrez répondre à l'appel, il sera ramassé. Lorsque votre code est capable de calculer les appels de fonction, il sort de la pile. N'oubliez pas cette métaphore lorsque vous regardez l'exemple de code suivant.

Récursivité numérique

Toutes les fonctions récursives nécessitent un cas de base afin qu'ils puissent se terminer. Cependant, l'ajout d'un boîtier de base à notre fonction ne l'empêche pas d'exécuter l'infini. La fonction doit avoir une étape pour nous rapprocher de la situation de base. Ceci est l'étape récursive. Dans l'étape récursive, le problème est réduit à une version plus petite du problème.

Supposons que vous ayez une fonction qui multiplie tous les nombres à partir de n. C'est ce qu'on appelle la fonction factorielle, nous l'écrivons comme 4!, Si n est égal à 1.

À chaque étape, vous soustrairerez 1 du numéro actuel. Quelle est la situation récursive? Le cas récursif est le fait de la fonction (4).

16. 4 est-il égal à 1? Non. Mettez le fait (3).
17. 3 est-il égal à 1? Non. Mettez le fait (2).
18. 2 est-il égal à 1? Non. Mettez le fait (1).
19. Est-ce que 1 est égal à 1? Oui. Renvoie le fait (2) et renvoie 2.
20. Obtenez 3 * fait (2) est un fait (4) et renvoie 24.

Voici une autre façon de voir comment la fonction gère chaque appel:

 <code>fact(4) 4 * fact(3) 4 * ( 3 * fact(2) ) 4 * ( 3 * ( 2 * fact(1) )) 4 * ( 3 * ( 2 * 1 ) ) 4 * ( 3 * 2 ) 4 * 6 24</code>

Dans les cas récursifs, les paramètres devraient changer et vous rapprocher du cas de base. Ce paramètre doit être testé dans les cas de base. Dans l'exemple précédent, parce que nous soustrayons 1 dans le cas récursif, dans le cas de base, nous testons si le paramètre est égal à 0.

défi

1. Implémentez la fonction SUM à l'aide de boucles au lieu de récursivement.
2. Créer une fonction qui multiplie de manière récursive deux nombres. Par exemple, 0;
3. Simplifie la fonction de filtre afin qu'elle supprime tous les éléments de la liste. Par exemple, ["A", "B", "D"].

Récursivité de la queue

La récursivité de la queue est une forme de récursivité qui permet au compilateur d'effectuer l'optimisation des appels de queue (TCO) pour empêcher de nombreux défauts de performance de la récursivité ordinaire. De plus, la récursivité de la queue résout le problème des appels de fonction maximaux de la profondeur. Cependant, vous devez écrire la fonction d'une manière ou d'une autre pour le faire fonctionner.

La récursivité de la queue convient aux fonctions qui appellent des fonctions récursives à la fin d'une fonction. Par exemple, voici la version récursive de la queue de la fonction sum (): la valeur de retour entière de sum () est la valeur de retour entière, de sorte que le temps d'exécution peut éliminer en toute sécurité la fonction externe et renvoyer uniquement les résultats de la fonction interne. Cependant, beaucoup de gens trébucheront sur quelque chose comme ceci:

 fonction nottailrecursive (n) {
    // ...
    retour nottailrecursive (n) 1
}

Vous pourriez penser que cela utilise la récursivité de la queue car la fonction récursive est appelée à la fin. Mais ce n'est pas le cas. En effet, JavaScript doit revenir à une fonction externe pour ajouter 1. L'une des façons dont vous pouvez la réécrire est de passer 1 dans l'argument afin que la fonction intérieure puisse faire ce calcul.

Tous les navigateurs ne prennent pas actuellement en charge l'optimisation des appels de queue, mais c'est dans la norme ES, nous pouvons donc en voir plus de support à l'avenir. De plus, c'est généralement une bonne pratique car il isole généralement les changements des paramètres de fonction.

défi

Reconstruire un exemple de fonction récursive dans cet article en une fonction récursive de queue.

Résumer

Il existe trois parties pour les fonctions récursives. Le premier est la situation de base, qui est la condition de terminaison. La seconde est l'étape qui nous rapproche de la situation de base. Le troisième est l'étape récursive, où la fonction s'appelle avec une entrée simplifiée.

La récursivité est comme l'itération. Toute fonction que vous pouvez définir récursivement ou utiliser une boucle. D'autres choses à considérer lors de l'utilisation de la récursivité incluent des listes imbriquées récursives et des appels récursifs optimisés.

Vous pouvez refacter la fonction récursive en une fonction récursive de queue, qui peut fournir des avantages de performance.

Une bonne ressource pour continuer à apprendre la récursivité est le livre The Little Schemer. Il utilise un format de questions-réponses pour vous apprendre à penser de manière récursive.

Ce message a été mis à jour avec les contributions de Jacob Jackson. Jacob est développeur Web, écrivain technologique, pigiste et contributeur open source.

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!