Home  >  Article  >  Web Front-end  >  How to understand recursion in JavaScript?

How to understand recursion in JavaScript?

PHPz
PHPzforward
2023-08-29 19:25:07687browse

如何理解 JavaScript 中的递归?

What is recursion?

The word recursion comes from recurring, which means going back to the past again and again. A recursive function is a function that calls itself again and again by changing the input step by step. Here, changing the input by one level means decreasing or increasing the input by one level.

Whenever a recursive function reaches a base condition, it stops its own execution. Let us understand what are the basic conditions through an example. For example, we need to find the factorial of a number. We call the factorial function by decrementing the input by 1 and need to stop whenever the input reaches 1. Therefore, here 1 serves as the basic condition.

grammar

Users can use the following syntax to understand recursion in JavaScript.

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

In the above syntax, users can observe that when the basic condition becomes true we return null to stop the execution of the function. If the base condition is false, we perform some action with the input value and call the recur() function again with the new parameter value.

Now, let’s look at various examples of recursion. Here we will learn to first implement an iterative algorithm using a for loop and then convert it into a recursive method.

Example 1 (Use a for loop to find the sum of 1 to n numbers)

In the following example, we have written the sumOfN() function to get the sum of 1 to N numbers. We use a for loop for N iterations and in each iteration we add the value of I to the sum variable.

Finally return the value of the sum variable.

<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>

In the above example, we use the iterative method to find the sum of N numbers. Now, we will use recursive method to do the same thing.

Example 2 (Use recursive function to find the sum of 1 to n numbers)

sumOfN() function is the recursive function in the example below. We repeatedly call the sumOfN() function by decrementing the value of the argument by 1. sumOfN(N1) returns the sum of N-1 numbers, we add N to it to get the sum of N numbers. Whenever the value of N becomes 1, it returns 1 as a base condition to stop the function execution.

<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>

Let’s understand how the above recursive function works. Below, users can learn step-by-step how recursive function calls occur.

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; 

Example 3 (Iteration method to merge all strings in an array)

In the example below, we create an array of strings. We created the mergeString() function to merge all the strings of the array into one string. We use a for loop to iterate through the array and merge all the strings into the "str" ​​variable one by one.

<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>

Example 4 (recursive method of merging all strings in an array)

In the example below, we have converted the mergeString() function into a recursive function. We take the first element of the array and merge it with the return result of the mergeString() function. The mergeString() function returns the last n-1 array elements after merging. Additionally, we use the slice() method to remove the first element from the array.

When there is only one element left in the array, it returns the same element as the base condition.

<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>

Which method should the user use, iterative or recursive?

The main question is which method is better, iterative or recursive, and which method the user should use.

In some cases, iterative methods are faster than recursive methods. Additionally, recursion requires more memory during iteration. For some algorithms like divide and conquer, recursion is more useful because we need to write less code using recursive methods. Additionally, users may face memory leak issues if basic conditions are not triggered in recursive methods.

If we can break the code into smaller parts, we should use recursive methods, and to improve the performance of the code, we should use iterative methods.

The above is the detailed content of How to understand recursion in JavaScript?. For more information, please follow other related articles on the PHP Chinese website!

Statement:
This article is reproduced at:tutorialspoint.com. If there is any infringement, please contact admin@php.cn delete