Recursion in JS for Beginners, avoiding an infinite loop

Recursion is tricky. First of all, as a beginner, we are just learning about functions and what they do. We feel happy with our progress until a teacher, youTuber or blog post helpfully drops recursion on us and we are floored: a function that calls itself? For lack of a better word, whaaaaa...???

In this blog post, I will address a few questions that I encountered when I first learned about recursion, mainly:

1. What is Recursion?
2. How does it work?
3. Why should I use it?

**Spoiler; the last question I am still answering for myself.

What is Recursion?

A recursive function is one that calls itself. It may look something like this:

function recursionFunction(num){
  if(num > 0){
    console.log(num)
    recursionFunction(num-1);
  };
};
recursionFunction(10)

//Prints 10 9 8 7 6 5 4 3 2 1 

Study the code above. Really look at what each element is doing; look at the curly braces, the parenthesis, the name of the function. Try to understand what the function is doing and describe it out loud to yourself. You can even open it up it this JavaScript REPL (make sure you are in node.js) and plug in the code to the left side and hit run.

Let's go through line-by-line, performing how JS performs, to better understand this process.

Line one: the function declaration

function recursionFunction(num)

Let's say out loud what this is saying:

"We are declaring a function called recursiveFunction that has one parameter, num.

Wonderful! Great technical communication. Now, JS stores this function (which is everything inside of the curly braces) in global memory, to be accessed when we call the function later in our program. The program moves on to the next line of code:

The Call to recursionFunction

recursionFunction(10)

This is the call for recursionFunction to execute with the passed in argument of 10. Since JS has this info stored in global memory, it can pull recursionFunction up again (remember, JS is synchronous, so it will not move up lines of code to access the function again; it will look for the stored function declaration in global memory.).

The Body of the Function

  if(num > 0)

Now, JS has entered a local execution context for the call to recursionFunction, and in the local memory, we are storing the argument at 10 (so currently, num = 10). In the next line of code, JS is reading "if 10 is greater than 0". This is called our "base case" and is so very important in recursion (more on this later). What that means is that, if this is true, go ahead and do the body of the "if" statement.

Is the if statement true or false right now?

That's right! It is totally true. Let's move on to the next line of code:

{
    console.log(num)
    recursionFunction(num-1);
  };

JS will then print num, which it has stored in this local memory as 10. Then, it will call recursionFunction again, but this time, the argument is (num -1). What is num? We have it stored in the local memory for the first call of recursionFunction; it is 10. So now, JS will open another execution context, on top of the first one, storing num-1, or 10-1, as the definition of num.

What do you think will happen next? We have a second execution context open, and num = 9. I think we will go back up to the stored function declaration of recursionFunction (which is stored where? In the Global Memory, meaning we can call it over and over again no matter where in our call stack we are) and use our second argument in place of our parameter num.

First we hit our base case:

if(num>0)

Is that true? Is 9 > 0? Absolutely, so we can move into the body of our base case and execute the code:

{
    console.log(num)
    recursionFunction(num-1);
  };

Now we print 9, and call recursionFunction passing in num (which is 9) minus 1. Now we open up yet another execution context, with our new argument at 8, and do everything all over again.

Now let's pretend we did all that, and now num = 0. We currently have 10 execution contexts stacked on top of each other (this is called the call stack). JS hits our base case, if num > 0... is it? Not anymore! We have finally hit the base case for this recursion. Our if statement evaluates to false, so JS exits the current execution context (which is recursionFunction(0)), enters the next one, sees there is nothing more to do there, and keeps going down the line until we are back in the Global Execution Context. Whew!!!

Base Case

As promised, let's talk a little more about our base case and code composition. What would happen to our recursive function if we moved the call to recursionFunction outside of the if statement body?

function recursionFunction(num){
  if(num > 0){
    console.log(num)
  };
  recursionFunction(num-1);
};
recursionFunction(10)

It is a simple change, we moved the code one line down. But go ahead and open up the REPL, see what happens when you plug this variation in.

Something like this will appear:

10
9
8
7
6
5
4
3
2
1
RangeError: Maximum call stack size exceeded
    at recursionFunction (/home/runner/tf3w0jc6kne/index.js:1:27)
    at recursionFunction (/home/runner/tf3w0jc6kne/index.js:5:3)
    at recursionFunction (/home/runner/tf3w0jc6kne/index.js:5:3)
    at recursionFunction (/home/runner/tf3w0jc6kne/index.js:5:3)
    at recursionFunction (/home/runner/tf3w0jc6kne/index.js:5:3)
    at recursionFunction (/home/runner/tf3w0jc6kne/index.js:5:3)
    at recursionFunction (/home/runner/tf3w0jc6kne/index.js:5:3)
    at recursionFunction (/home/runner/tf3w0jc6kne/index.js:5:3)
    at recursionFunction (/home/runner/tf3w0jc6kne/index.js:5:3)  

Ouch, that is painful! See where it says

"Maximum call stack size exceeded
at recursionFunction"?

JavaScript is throwing us this error because we are recursively calling recursionFunction outside of our base case declaration (the "if" statement right at the beginning).

WAIT, WAIT...WHAT???

Think about it like this: we are calling a function from the body of itself. Which means we are inherently setting up the stage for an infinite loop. If we don't tell JS, "Hey wait! Stop running this loop when you hit zero. You don't need to go past zero and into the forever underworld of negative numbers. We good at 0.", then it doesn't know to stop. JS is performative and does not make judgement calls; it will simply go on doing what we ask of it until our memory doesn't allow it to happen any more. And then our program crashes.

To avoid that, when we write our recursions, let's make sure that our recursive call is within the code block where our base case has power.

Space and Time Complexity

That was a simple demo for what recursion can do for you as a programmer. It can make life easier for you, but it does take up more memory. Remember the call stack we talked about? Because recursive functions need to maintain this stack when they are being called, they use more space than an iteration would. They also have a slower processing rate.

HOLD ON: if recursion is slower and takes more space to process than an iteration...

...why wouldn't we just use an iteration, like a for loop or a forEach()?

const nums = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1];

function printNums(number){
  for(let i = 0; i<number.length; i++){
    console.log(number[i])
  }
}
printNums(nums)
//prints 10 9 8 7 6 5 4 3 2 1

In many imperative situations, iteration is favored way above recursion. However, there are some specific situations where the code to write an iteration is too complex, and recursion is necessary. One of these situations includes Tree Traversal. Click on the link if you are feel confident with recursion and are looking for some meaty methods for solving algorithms. If algorithms are a new idea and you feel like a firehose just blasted you with info, take a breath, and lets go back to the recursive code we started with and practice our technical communication:

Technical Communication

function recursionFunction(num){
  if(num > 0){
    console.log(num)
    recursionFunction(num-1);
  };
};
recursionFunction(10)

//Prints 10 9 8 7 6 5 4 3 2 1 

We are declaring a function called recursionFunction that accepts a parameter, num. The body of the function first establishes a base case: if num is greater than zero, print num. Then call recursionFunction again, passing in the argument of num minus one. We then exit the body of our base case, and exit the body of our function, and call recursionFunction passing in the integer ten as our argument. This begins the recursion process.

Great job! You just tackled one very tricky topic in your path to understand JavaScript. Give yourself a pat on the back, and go celebrate your win.

Happy Coding!