Recursion and the Call Stack Explained By Reading A Book

Recursion is one of the most exciting principles of all programming languages.

A non-recursive function (in other words, the functions that you have used in the past) will run once every time it is called, and output via a return statement.

However, a recursive function can be called once and then call itself an undetermined number of times before combining the output of all the function calls in one return statement.

It kind of looks like this.

Static version:

Dynamic version:

The idea that a single function can be called one to infinity times via a single statement is what makes it so exciting!

At the same time, it is difficult to think of a real-world analogy to this situation. And it gets especially difficult once we discuss the call stack , which we will cover later.

Some have suggested a series of infinite boxes:

Image Cred: Grokking Algorithm

Others have suggested the imagery of “Russian nesting dolls”:

However, this is also unhelpful when understanding the call stack.

So, in this tutorial, we will show two popular examples of recursion, and build a visual language for understanding the function and the call stack , which determines how to make sense of the many function calls in a row.

Before continuing with this tutorial, you should have a firm understanding of functions in JavaScript. Check out this guide to arrow functions to learn more.

Example 1- Factorials

Factorials are the most popular example of recursion.

You might be familiar with factorials from algebra class.

They are expressed like: 3!

And that notation evaluates to 3*2*1, or 6.

We could express this as a “for” loop where we update a variable outside the loop:

let factorial = 4;
let result = 1;

for (i=factorial; i>= 1; i--){
    result = result*i;
}

But, here we will use recursion instead. Rather than have a loop that updates a variable outside of its scope, we can use recursion with a function and have n-1 calls, where n is the factorial we want to find.

I will show the code first, and then we can evaluate how it works.

let getFactorial = (num) => {
  if (num == 1)
    return 1;
  else
    return num * getFactorial(num-1);
}

getFactorial(4);
// 24

Woah! This accomplishes the same thing as the code block above.

But, if you look at line 5, you can see that the return statement includes a reference to the function itself.

So… when does this function return a final value, exactly? How do we link the 4 calls of the function together to return the value of 24?

This is where the call stack becomes useful. It determines the rules for the order that these function calls will return.

But, now we are stacking two concepts on top of each other: recursion and call stack. That’s a lot at once.

In order to visualize the call stack, let’s think of a stack that builds from left to right. Every time a block gets added, it is added to the left side of the stack and pushes the other blocks to the right.

So, as we go through this recursive function, we generate a stack like this:

The call stack is being generated at the bottom of the screen throughout the GIF above. At the end, we are left with 1*2*3*4 which results in 24.

The call stack is composed of 4 function calls, and none of them run until the function returns 1. They sit on the stack until the last value is added, in this case 1.

This is because each of the first 3 calls includes a reference to the next call on the stack!

So, when num=4, the function returns 4*getFactorial(3). Of course, that cannot actually return a value until we know the value of getFactorial(3). That’s why we need a call stack!

So, recursion allows a function to be called an indefinite number of times in a row AND it updates a call stack, which returns a value after the final call has been run.

The call stack updates from left to right, and then you can read all the calls in the order they are resolved. Most recent is resolved first, first call resolved last.

However, our GIF above did not do a good job of showing this relationship between each call. So, here’s an updated version that shows how all the calls are connected via the return statement:

Example 2- Splitting a String

In the example above, we used a mathematical example that resembled a question from algebra class.

This works, but there are also plenty of examples of recursion that go beyond math. In this example, we will show how you can use recursion to manipulate a string.

Here’s the challenge: Reverse a string.

In other words, return a string with the letters of an input string in the opposite order.

You can also do this with a “for” loop, but we will use recursion in this example.

Let’s think about how we should reverse the string “cat”.

Every time we run a function call, we need to isolate the first or last letter of the string, and then chop off a letter from the string. When we run the function again, we should again grab the first or last letter.

At the end, the call stack will allow us to return the letters in the correct order.

Here’s the code:

let testStr = 'cat';

let revStr = (str) => {
  if (str.length == 0)
    return '';
  else
    return revStr(str.substr(1)) + str[0];
};

revStr(testStr);
// 'tac'

Okay. Let’s dig in, just like we did above.

Again, although the GIF above makes it look easy, we need to dig deeper into the final return statement if we want to truly understand these function calls.

There is one more important difference in this example compared to the one above- we are doing string concatenation rather than multiplication.

Therefore, the order of the strings in that return statement matters quite a bit, because it determines which order we will use for concatenation.

Since this is not a series of multiplication problems, the call stack is a little easier to understand. Here is a visual:

This is why the order of the strings matters so much- as we build the call stack in the GIF above, there is a specific order of the recursive function call and the string fragment (str[0]).

As we run all the calls in the stack, this order allows us to rebuild the string in the reverse order.

Get The Latest Tutorials

Did you enjoy this tutorial? Check out the CodeAnalogies blog to get the latest visual web development tutorials.