It took me several attempts to understand recursive functions.

Once I understood how it works, I figured I didn't completely understand 2 things:

1. Function’s Return Value
2. The Callstack

Once I understood these 2, recursion made sense.

This post is how I’d teach my beginner-self recursion if I could go back.

#1 Function’s Return Value

When a function returns a value, the function itself is replaced by the return value.

Let me try to exemplify:

This is a function that returns the square of a number

function square(x) => x * x;

This:

const num = 1 + square(3);

Is the same as:

const num = 1 + 9;

square(3) is "replaced" by 9, since 9 is the value that the function returned.

Cool? Great.

Do you remember that in Maths sometimes the order or the operations mattered? This is the case when working with functions. The code interpreter can’t add 1 to square(3) before it knows what the heck is the value of that square(3) returns. So functions have to be executed before the other calculations on the same line.

Example:

function square(x) => x * x; //line 1
const num = 1 + square(3);   //line 2
console.log(num) //10        //line 3

The interpreter will run the above code in the following order:

1. Line 1 (read the function declaration)
2. Line 2 (Oh there is a function here, let's call this function passing the value 3 into it)
3. Line 1 (function is called with 3 and returns with the value 9)
4. Line 2 (it replaces the function with 9 and now can calculate 9 + 1 and assign it to num)
5. Line 3 Finally we log 10 to the console.

The takeaway is that every time there is a function call, the interpreter:

• Stops on that line and calls the function
• It runs the function code with the value passed in(if any)
• It goes back to the line that called it
• Replaces the function call with the returned value
• Resume from there

It is essential to understand this to understand recursion(this was one of the things I had problems with that made it harder to understand recursion).

#2 The Callstack

The call stack is how the interpreter(like the javascript interpreter in this browser) keeps track of the functions called by the script.

That is how the interpreter knows how to come back to the line that has called the function.

I’d like to think of it as a box to store the books you read and in which page and line you stop at each.

Say you are in your local library.

You start reading the book “Sapiens”. On page 72 line 87 it mentions the diprotodon(the biggest marsupial to walk on earth) which itches your curiosity. So you put a marker on the page and write down the line you are at and put the book in the box.

Then you find a book about the diprotodons. But on page 94 line 138 it mentions the giant sloths and again curiosity kicks in. You put a marker on page 94 and write the line you are at on it and put it in the box.

As you read more about the giant sloths you realize it’s time to go home. You put another marker on page 121 line 147 and put the book in the box.

The next morning you rush to the library to finish your readings.

How do you know in what book, page, and line you left off? Since you were organized with your stack of books and markers, the answer is easy. Just pick the top book from the box, the marker inside the book will tell the page and line.

Know you can make your way back to the initial book("Sapiens") and keep reading until the end(or until curiosity strikes again)

The analogy is:

1. The box is the call stack
2. Each book is a function call
3. Each marker is in which line the function was called

If I'd translate this example into code it would look something like this:

function readSapiens(){
   //read until page 72 line 87
   readDiprotodonsBook();
   //finish reading sapiens(when we are back from reading about diprotodons)
}

function readDiprotodonsBook(){
   //read until page 94 line 138
   readGiatSlothsBook();
   //finish reading diprotodon's book(when we are back from reading about giant sloths)
}

function readGiatSlothsBook(){
   //read until page 121 line 147
   debugger
}

readSapiens();

If you hit f12 now, copy this code, paste it on the console, hit enter, and go to the sources tab you can see the call stack.

It will look like this:

The code is paused inside the third function call.

See that there is no magic, everything is built on top of data structures.

Now we are prepared to go over an actual recursive function example.

Basic Example

The simplest example I can think of is a function that adds all numbers until the number you passed in.

function addNums(x){
   if(x === 1) return x;
   return x + addNums(x - 1);
}

Note: I am not taking into account 0 or negative numbers to simplify the example.

addNums(3) //6
addNums(5) //15

Let's go through it line by line:

function addNums(x){          //line 1
   if(x === 1) return x;      //line 2
   return x + addNums(x - 1); //line 3
}                             //line 4
                              //line 5
let sumThree = addNums(3);    //line 6
console.log(sumThree); //6    //line 7

1. [Lines 1 to 5]: Smooth execution, it just declares the function(now we can call it when need to)

2. [Line 6]: The interpreter declares the variable sumThree but before it assigns the value addNums(3) he realizes that it is a function, so it has to call the function first(passing 3 into it) to then assign the return value to the variable sumThree

2.1. [Waiting on Line 6]: It calls the function on line 1, passing 3 into it. 3 is not equal to 1 so we move past line 2. On line 3 we should return 3 + addNums(3 - 1) but wait, this is another function call. So it has to call it first passing 2 into it.

2.2. [Waiting on Line 6 [waiting on Line 3]]: It calls the function on line 1, passing 2 into it. 2 is not equal to 1 so we move past line 2. On line 3 we should return 2 + addNums(2 - 1) but wait, this is another function call. So it has to call it first passing 1 into it.

2.3. [Waiting on Line 6 [waiting on Line 3 [waiting on Line 3]]]: It calls the function on line 1, passing 1 into it. This time we hit the base case. 1 === 1 is true, so for the first time we return a value from a function call.

2.4. [Waiting on Line 6 [waiting on Line 3]]: It goes back to line 3 of the previous function call. It now can calculate 2 + addNums(2 - 1) because it now knows that addNums(2 - 1) is 1. So this function now can return 3.

2.5. [Waiting on Line 6]: Lastly it goes back to the initial call on line 6. It can now calculate 3 + addNums(3 - 1) because it now knows that addNums(3 - 1) is 3. So this function now can finally return 6.

1. [Line 7]: It logs 6 to the console.

I also tried to explain it visually(to the best of my abilities), have a look:

Conclusion

If you read this far, first I want to thank you, it means a lot to me. Second, if you got lost at any point in this post, can you do me a favor?

Leave a quick comment saying where I lost you.

I'll try to improve this post so it can help you that like me once had a hard time understanding recursion.

Thanks again for reading!

If you like this article:

Leave a comment (You can just say hi!)
Let's connect on Twitter @theguspear

Catch you next week,

Gus.