How to understand recursion in 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.

  
Using the  iterative approach  to find sum of n numbers in JavaScript
 
 
   

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.

  
Using the  recursive approach  to find sum of n numbers in JavaScript
 
 
   

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.

  
Using the  iterative approach  to merge all strings of the array in JavaScript
 
 
   

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.

  
Using the  Recursive approach  to merge all strings of the array in JavaScript
 
 
   

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!