Maison  >  Article  >  interface Web  >  Comment comprendre la récursivité en JavaScript ?

Comment comprendre la récursivité en JavaScript ?

PHPz
PHPzavant
2023-08-29 19:25:07684parcourir

如何理解 JavaScript 中的递归?

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

Le mot récursivité vient de récurrent, ce qui signifie revenir encore et encore dans le passé. Une fonction récursive est une fonction qui s'appelle encore et encore en modifiant l'entrée étape par étape. Ici, modifier l'entrée d'un niveau signifie diminuer ou augmenter l'entrée d'un niveau.

Chaque fois qu'une fonction récursive atteint une condition de base, elle arrête sa propre exécution. Comprenons quelles sont les conditions de base à travers un exemple. Par exemple, nous devons trouver la factorielle d’un nombre. Nous appelons la fonction factorielle en décrémentant l'entrée de 1 et devons nous arrêter chaque fois que l'entrée atteint 1. Par conséquent, ici 1 sert de condition de base.

Grammaire

Les utilisateurs peuvent utiliser la syntaxe suivante pour comprendre la récursivité en JavaScript.

function recur(val) {
   if (base condition) {
      return;
   }
   
   // perform some action
   
   // decrease the value of val by one step
   return recur(newVal);
}

Dans la syntaxe ci-dessus, les utilisateurs peuvent observer que lorsque la condition de base devient vraie, nous renvoyons null pour arrêter l'exécution de la fonction. Si la condition de base est fausse, nous effectuons une action avec la valeur d'entrée et appelons à nouveau la fonction recur() avec la nouvelle valeur du paramètre.

Maintenant, regardons divers exemples de récursivité. Ici, nous allons apprendre à d'abord implémenter un algorithme itératif à l'aide d'une boucle for, puis à le convertir en méthode récursive.

Exemple 1 (Utilisez une boucle for pour trouver la somme de 1 à n nombres)

Dans l'exemple ci-dessous, nous avons écrit la fonction sumOfN() pour obtenir la somme de 1 à N nombres. Nous effectuons N itérations en utilisant une boucle for et à chaque itération nous ajoutons la valeur de I à la variable somme.

Renvoie enfin la valeur de la variable somme.

<html>
<body>
   <h3>Using the <i> iterative approach </i> to find sum of n numbers in JavaScript</h3>
   <div id = "content"> </div>
   <script>
      let content = document.getElementById('content');
      
      // function to find the sum of n numbers using an iterative approach
      function sumOfN(n) {
         let sum = 0;
         for (let i = n; i >= 1; i--) {
            sum += i;
         }
         return sum;
      }
      content.innerHTML += "The sum of 1 to 10 numbers is " + sumOfN(10) + "<br>";
      content.innerHTML += "The sum of 1 to 20 numbers is " + sumOfN(20) + "<br>";
   </script>
</body>
</html>

Dans l'exemple ci-dessus, nous avons utilisé la méthode itérative pour trouver la somme de N nombres. Nous allons maintenant utiliser la méthode récursive pour faire la même chose.

Exemple 2 (Trouver la somme de 1 à n nombres à l'aide d'une fonction récursive)

La fonction

sumOfN() est la fonction récursive dans l'exemple ci-dessous. Nous appelons à plusieurs reprises la fonction sumOfN() en décrémentant la valeur de l'argument de 1. sumOfN(N1) renvoie la somme de N-1 nombres, on y ajoute N pour obtenir la somme de N nombres. Chaque fois que la valeur de N devient 1, il renvoie 1 comme condition de base pour arrêter l'exécution de la fonction.

<html>
<body>
   <h3>Using the <i> recursive approach </i> to find sum of n numbers in JavaScript</h3>
   <div id = "content"> </div>
   <script>
      let content = document.getElementById('content');
      
      // function to find the sum of n numbers using a recursive approach
      function sumOfN(n) {
         
         // base condition
         if (n == 1) {
            return 1;
         }
         
         // call function recursively by decreasing the value of n by 1.
         return n + sumOfN(n - 1);
      }
      content.innerHTML += "The sum of 1 to 10 numbers is " + sumOfN(10) + "<br>";
      content.innerHTML += "The sum of 1 to 20 numbers is " + sumOfN(20) + "<br>";
   </script>
</body>
</html>

Comprenons comment fonctionne la fonction récursive ci-dessus. Ci-dessous, les utilisateurs peuvent découvrir étape par étape comment les appels de fonction récursifs se produisent.

sumOfN(5);
return 5 + sumOfN(4);
   return 4 + sumOfN(3);
      return 3 + sumOfN(2);
         return 2 + sumOfN(1);
            return 1;
         return 2 + 1;
      return 3 + 3;
   return 4 + 6; 

Exemple 3 (Méthode itérative pour fusionner toutes les chaînes d'un tableau)

Dans l'exemple ci-dessous, nous avons créé un tableau de chaînes. Nous avons créé la fonction mergeString() pour fusionner toutes les chaînes du tableau en une seule chaîne. Nous utilisons une boucle for pour parcourir le tableau et fusionner toutes les chaînes dans la variable "str" ​​​​une par une.

<html>
<body>
   <h3>Using the <i> iterative approach </i> to merge all strings of the array in JavaScript</h3>
   <div id = "content"> </div>
   <script>
      let content = document.getElementById('content');
      
      // function to merge all strings of the array using for loop
      function mergeString(arr) {
         let str = '';
         for (let i = 0; i < arr.length; i++) {
            str += arr[i];
         }
         return str;
      }
      let arr = ['I', ' ', 'am', ' ', 'a', ' ', 'programmer'];
      content.innerHTML += "The original array is: " + arr + "<br>";
      content.innerHTML += "After merging all strings of the array into the single string is " + mergeString(arr) + "<br>";
   </script>
</body>
</html>

Exemple 4 (méthode récursive de fusion de toutes les chaînes d'un tableau)

Dans l'exemple ci-dessous, nous avons converti la fonction mergeString() en fonction récursive. Nous prenons le premier élément du tableau et le fusionnons avec le résultat de retour de la fonction mergeString(). La fonction mergeString() renvoie les n-1 derniers éléments du tableau après la fusion. De plus, nous utilisons la méthode slice() pour supprimer le premier élément du tableau.

Lorsqu'il ne reste qu'un seul élément dans le tableau, il renvoie le même élément que la condition de base.

<html>
<body>
   <h3>Using the <i> Recursive approach </i> to merge all strings of the array in JavaScript</h3>
   <div id = "content"> </div>
   <script>
      let content = document.getElementById('content');
      
      // function to merge all strings of the array using recursion
      function mergeString(arr) {
         
         // based condition
         if (arr.length == 1) {
            return arr[0];
         }

         // remove the first element from the array using the slice() method.
         return arr[0] + " " + mergeString(arr.slice(1));
      }
      let arr = ["I", "am", "a", "web", "developer"];
      content.innerHTML += "The original array is: " + arr + "<br>";
      content.innerHTML += "After merging all strings of the array into the single string is " + mergeString(arr) + "<br>";
   </script>
</body>
</html>

Quelle méthode l'utilisateur doit-il utiliser, itérative ou récursive ?

La question principale est de savoir quelle méthode est la meilleure, itérative ou récursive, et quelle méthode l'utilisateur doit-il utiliser.

Dans certains cas, les méthodes itératives sont plus rapides que les méthodes récursives. De plus, la récursivité nécessite plus de mémoire lors de l'itération. Pour certains algorithmes comme diviser pour régner, la récursivité est plus utile car nous devons écrire moins de code en utilisant des méthodes récursives. De plus, les utilisateurs peuvent être confrontés à des problèmes de fuite de mémoire si les conditions de base ne sont pas déclenchées dans les méthodes récursives.

Si nous pouvons diviser le code en parties plus petites, nous devons utiliser des méthodes récursives, et pour améliorer les performances du code, nous devons utiliser des méthodes itératives.

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!

Déclaration:
Cet article est reproduit dans:. en cas de violation, veuillez contacter admin@php.cn Supprimer