Recursion

Recursion can be an intimidating topic to tackle, and it certainly does get complex and takes some thinking, but actually the basics of it are pretty simple and it's easy to get going with. The basic idea is, you take a problem, do it over and over again on a smaller or changing piece until you hit an endpoint. In our case, that means it's a function that calls itself itself.

 

In order to get started with recursion we need to have an understanding of and visualize the call stack, and we need to understand the two essential components of a recursive function. 

 

The Call Stack

The Call Stack is a data structure the JavaScript engine uses to manage Execution Contexts. Whenever a function is called, the JavaScript engine creates a Function Execution Context for it, pushes it on top of the Call Stack, and starts executing the function. When the function completes, the JavaScript engine pops it off the call stack. In order for the function to "complete", we have to return a value using the return keyword. If a function calls another function, the JavaScript engine creates a new Function Execution Context for the function that is being called and pushes it on top of the call stack. We'll try to visualize what this looks like with some examples, after we talk about the two essential components of a recursive function.

 

Base Case & Changing Input

When we're calling a function from inside of itself, we have to have two things in order to make sure the function doesn't just keep running indefinitely, like an infinite loop.

 

We have to define when the function should stop. We do this by defining a Base Case (a condition where the recursion ends) and then we have to make sure we're passing the function a different input that works its way towards achieving that Base Case.

 

If you do either of these things wrong, the recursion will continue spinning its wheels without achieving its purpose until it hits the maximum call stack size allowed by that engine and returns an error. This is referred to as stack overflow, which is where the name for the popular q&a site for developers comes from.

 

Now let's dive into an example and see what this looks like:

 

function countDown(num) {
    if(num <= 0) {
        console.log('All done!');
        return;
    }
    console.log(num);
    num--;
    countDown(num);
}

 

Let's say we run countdown(3);:

 

The first time we call countDown() we pass it the initial value of 3 as num. 3 > 0 so we log num (3), decrease num by 1, and call the function again with the new num (2) passed into it. So our input is changing each time until we reach our Base Case which is num <= 0, at which point we console.log('All done!'), return the function, and the recursion ends.

 

Our end result on the console would be:

 

3

2

1

All done!

 

This is a simple example where we can see our input is changing, and we have a Base Case to get to and return to stop the recursion.

 

Building on from our first example

The purpose of this function is to add together than range of numbers from the input down to 1. A recursive function to do this would look like this:

 

function sumRange(num) {
    if(num === 1) return 1;
    return num + sumRange(num - 1);
}

 

First, let's identify the Base Case. Here, it is num === 1. It's a bit harder to spot the different input and visualize how we're getting to our base case and what our final return value will be because we're not just printing, we're returning over and over again. So let's break it down.

 

Let's say we call sumRange(3):

On the first go-round, we'll skip our Base Case because num doesn't equal 1. This means we're going to return 3 + sumRange(2). The engine doesn't know yet what sumRange(2) is, so it will remain in the Call Stack and wait for a value to be returned as it adds sumRange(2) to the top of the Call Stack.

 

We'll go through the same process with sumRange(2), because num doesn't yet equal 1, it equals 2. So sumRange(2) will return 2 + sumRange(1) and the engine will keep that in the Call Stack and wait to see what comes back from sumRange(1).

 

Now, num === 1 so we've reached our base case and that will return 1.

 

Now that sumRange(2) knows that sumRange(1) is returning a value and not another function it can complete its calculation of 2 + 1 and return 3.

 

Now that sumRange(3) knows what number sumRange(2) is returning, it can complete its calculation and return 3 + 3, or 6.

 

Now that there are no other functions in the call stack, the recursion is done, and we'll get the value 6 returned as our final result, which equals 3 + 2 + 1, which is what we wanted.

 

Recursive Functions vs Iterative Functions

You probably noticed that neither of these examples were too complex, or anything we couldn't have solved with a for loop. This approach, which you'd probably use up til now if you're just learning about recursion, is called iteration. An iterative sumRange() function would look like this:

 

function sumRange(num) {
    let total = 0;
    for(let i = num; i > 0; i--) {
        total += i;
    }
    return total;
}

 

Both functions would get the same result with the same input. So, which is better? It often comes down to preference and the situation. Usage of either of these is a trade-off between time complexity and size of code. Recursive functions allow you to write elegant solutions that require much less code, but can be more difficult to understand and execute slower as it repeatedly invokes the overhead of function calls.

 

If time complexity is the point of focus, and number of recursive calls would be large, it is better to use iteration. It can also be better to use iteration when other people maintaining your code is a concern, as recursion can be more difficult to understand for more complex solutions. However, if time complexity is not an issue and shortness of code is, recursion would be the way to go.