JavaScript Recursion (with Examples)

 

Javascript is a versatile programming language that offers various techniques for solving problems including Recursion. In this article, we will learn, What recursion is, why and when to use it, and how it works in JavaScript with our examples. By the end of this article, you will have a good hold on recursion. Let’s get started!

What is Recursion?

Recursion is a programming pattern that involves solving a task by breaking it down into smaller, more manageable subproblems until a base condition is met.

It shortens down the code into fewer lines of code. It is used when solving a task develops a new similar task and these new tasks are solved with the same technique as used in the initial task. Hence for every new smaller input the same function is called repeatedly, and then comes a point where we meet the base case, and the problem gets solved.

Recursion involves a series of function calls, and also it keeps track of the current execution state in a call stack.

Understanding Recursive Functions

Recursive functions call themselves within their own body. It can be broken down into three components: the function declaration, the base case, and the recursive call.

The Function Declaration

The function declaration defines the recursive function and specifies any necessary parameters, serving as the starting point of the recursion process. Similar to any regular JavaScript function we can name it according to our preference. For example:

// myRecursiveFun is declared
function myRecursiveFun() {
  // body
}

The Base Case

The base case is the condition that determines when the recursion should stop, meeting the base case stops further calling of the function and returns the result:

// myRecursiveFun is declared
function myRecursiveFun(){
    if(base condition){
        //stops the recursion and return this value
    }
    // continue recursion
    myRecursiveFun();
}

If we do not have a base case then recursion will never stop and will cause a “maximum call stack exceeded” error, known as infinite recursion.

The Recursive Call

The recursive call is the command that triggers the function to call itself again with a different input, moving closer to the base case.

Here each time the same set of operations are applied on a smaller input until the base case is reached. Each recursive call is applied to a smaller subset of the original problem, eventually leading to the result:

// myRecursiveFun is declared
function myRecursiveFun(){
    //some code
    myRecursiveFun();
}

How Recursion Works in JavaScript?

When a recursive function is called, it goes through a series of recursive calls until the base case is reached, at this point, the function starts to unwind and combines the result from each level of recursion to obtain the final result.

Let’s take an example of a sum function, which returns the sum of the first n natural numbers:

// function sum is declared
function sum(n){

    //base case
    if(n<=1)return 1;

    // Recursive call
    return n+ sum(n-1);
}
//displays result of calling sum function with argument 4
console. log(sum(4));

Output:

10

Let’s take a look at the sequence of steps:

• To calculate the sum of the first four natural numbers, we will call the sum with an argument of 4.
• Since 4 is not equal to or less than 1, the function makes a recursive call to sum(3).
• Again, the function checks if the argument is less than or equal to 1. As 3 is greater, it makes another recursive call to sum(2).
• This process continues until the function reaches sum(1), as in this call, the function reaches base case and 1 is returned.
• The intermediate results are propagated back up the call stack, and the final result is calculated by adding the current number to the result of the recursive call.
• In this case, it is 4+3+2+1 = 10, which is returned as the result of the initial sum(4) call.

Here we can see each call waits for its inner call to return before proceeding. Once we reach the base case, the chain starts unwinding and the results are calculated and propagated back up the call stack.

Why Use Recursion?

Recursion offers a lot of advantages that make it a powerful technique for solving complex problems:

1. It makes the code more readable and easier to understand as it often requires fewer lines of code compared to iterative solutions.
2. These functions can be reused to solve other similar problems with different inputs. Once implemented, we can apply them to various scenarios without rewriting the entire solution.
3. It follows the “divide and conquer” approach, which breaks down a problem into smaller subproblems.
4. Recursive functions are modular and self-contained, which makes it easier to identify and isolate potential issues.

When Not to Use Recursion?

Although recursion is a powerful technique, it is not suited for every situation. Let’s discuss a few scenarios where it may not be the best choice:

• As we know with each recursive call, a new frame is added to the call stack, so if our input is large, it may lead to stack overflow errors or slower execution times. If optimal performance is a priority, we should explore alternative methods such as iteration or employing tail recursion.
• These functions often have higher memory usage as compared to iterative solutions. The creation of a new stack frame with each recursive call leads to increased memory consumption. Therefore if memory usage is a concern, we should explore alternate solutions.
• Without proper base cases or termination conditions, these functions should not be used. It will lead to infinite recursion, leading to stack overflow, and the application crashes.

Conclusion

Now we have a thorough grasp of recursion. We have covered its fundamentals in JavaScript, along with some examples. Also, we know when to use and when to not, because sometimes it can lead to memory and speed issues. Iterative solutions can be applied there, learn more from Recursion VS Iteration to find the difference.