Introduction to Recursion in JavaScript

Recursion has struck fear into the hearts of almost everyone who has opened an IDE, typed the magical command that printed “Hello, World!” in your terminal, and attempted to learn the ins and outs of the web’s most used programming language: JavaScript. While recursion has a nuance that must be learned and respected, the core idea is rather simple. A recursive function is a function that calls itself.

‍
Our goal is to demystify Recursion and help you understand when and why to use it, because in the correct context, it is a valuable tool. Speaking of context, a quick refresher on how functions run can make the examples ahead much easier to follow. You can check out Codesmith’s “Functions and Execution Context” here to get a leg up, but if you are already familiar, let’s move on.

In this article, we will discuss:

• What is recursion?
• The three core parts of a recursive function
• Why you might use recursion
• What’s really happening under the hood in a recursive function
• When to use recursion
• Common pitfalls when building a recursive function
• Where to get started building with recursion

What Is Recursion? 

To put it simply, recursion is when a function solves a problem by invoking itself with smaller versions of that problem. Recursion always needs a way to stop, so each function must have a “base case”otherwise it would run forever resulting in “stack overflow”. The function will continue to invoke itself over and over again until it reaches this “base case”.

‍

The function above will continue to invoke itself until num is strictly equal to zero. If num is not equal to 0, it will:

• log ‘hi!’ to the console
• decrement the passed in num by one
• invoke itself again. 

This pattern will repeat until num is finally strictly equal to 0, then it will stop.

Like most things in JavaScript, there are several ways to achieve this goal.

Above, the base case is slightly different: if(num <= 0) return. This is a bit safer as it accounts for the possibility of a num having a negative value.

‍

You might also notice how, instead of decrementing num and then invoking sayHi with the new value, we’ve passed num - 1 as the argument itself to the recursive sayHi call. 

‍

In this case, both work just fine! It’s up to you to decide what makes the most sense for you and engineers who may be looking at your code in the future.

Core parts of recursion

Each part of a recursive function works together to achieve a single goal. Once the Base Case is defined, the Recursive Statement drives the function toward it.

In the example above, the Base Case triggers when the “times” variable becomes less than or equal to zero. To reach that point, the recursive statement calls the function again, reducing “times” by one on each call. In other words, the function will run the same number of times as the starting value of “times”, gradually moving closer to the Base Case until it finally returns our ending string: “Done!”

Why Use It?

Recursion shines when a problem can be broken down into smaller versions of itself. Instead of writing layers of loops or infinite “if” statements, a recursive approach can express the same idea in fewer lines with better readability. Basically it helps your team understand what you’re trying to accomplish without reading dozens of lines of code.

It’s especially useful for:

• Tree-like structures such as the DOM or JSON, where each branch can be processed the same way as the whole.
  
  
• Nested or repeating patterns like folder systems, mathematical sequences, or puzzles such as mazes and the Fibonacci sequence.
  
  
• Replacing deep or nested loops when iteration becomes messy or difficult to track.
  
  

Recursion can make code feel closer to the way we naturally describe these problems: “to solve the big problem, solve a smaller one first.” When written clearly and used in the right context, it creates elegant, maintainable solutions that mirror the structure of the problem itself.

What’s Happening Under the Hood

‍

Before diving into recursion, let’s first look at a simple loop example to build some context into the behavior of the call stack and  execution context (see what we did there?) . In this loop-based function, you’ll notice that even though it counts down from 3 to 0, only one frame will ever get added to the call stack. 

Using a standard for…loop

‍

However, in the recursive version of the same function, each recursive call pushes a new frame onto the call stack as the function works its way down from 3 to 0. Below, the countdown function invokes itself and decrements its input (num) with each call, moving closer and closer to the base case. Every single invocation pushes a new frame onto the call stack and opens up a brand new execution context.

Using recursion

‍

1. The function countdown(n) is first defined and stored in global memory.
2. Nothing is on the call stack yet (aside from our Global Execution Context).
3. The function is invoked, passing the number 3 in as the argument - countdown(3).

‍

1. countdown(3) is pushed onto the call stack and gets its own local execution context.
2. Local memory stores n: 3 (also known as pairing arguments with parameters)
3. Base case (n === 0) fails, so we console.log(3), then prepare to call countdown(2)

‍

1. A new frame for countdown(2) is pushed to the top of the call stack and another local execution context opens up.
2. Local memory stores n: 2.
3. The base case (n === 0) fails again. So, we console.log(2), then prepare to call countdown(1).

‍

1. countdown(1) is pushed on top of the stack and yet another local execution context opens.
2. Local memory stores n: 1.
3. The base case (n === 0) still fails, so we console.log(1) then prepare to call countdown(0).

‍

1. countdown(0) is pushed to the top of the callstack and another new execution context opens.
2. Local memory stores n: 0.
3. Our base case (n === 0) finally passes, so we immediately return without logging.
4. This local execution context now closes and becomes eligible for garbage collection. Its stack frame is then popped off (removed from) the top of the callstack.

‍

1. Control returns to the suspended countdown(1) frame after its recursive call.
2. With its recursive call complete, countdown(1) also now finishes. 
3. This execution context will now close, get garbage collected, and its frame will pop off the top of the callstack.

1. Control returns to countdown(2) now that its recursive call is complete.
2. countdown(2) is now finished executing.
3. This execution context will now close, get garbage collected, and its frame will pop off the top of the callstack.

‍

1. Control returns to countdown(3) now that its recursive call is complete.
2. countdown(3) is now finished executing.
3. This execution context will now close, get garbage collected, and its frame will pop off the top of the callstack.

‍

With all of its execution contexts closed and frames popped off the call stack, countdown(3) has officially finished running. Control has now returned to our Global Execution Context and, as we see, 3, 2, 1 have all been logged to the console.

‍

‍

When to use recursion

As you saw in the for…loop example above, loops are more memory efficient than recursion. Using a single loop, one frame was added onto the callstack as opposed to our recursive examples in which each function continued to invoke itself, pushing more and more stack frames onto the callstack. As a recursive function keeps calling itself, the stack grows until the base case is reached and the calls start returning.

That’s why recursion, while elegant, can use more memory than a loop that does the same task. So when should you use recursion?

So, yes, loops are more memory-efficient than recursion, but sometimes a recursive approach is much easier to reason about. That’s especially true for problems that involve more complex structures like trees, parsing JSON, and exploring file systems.

In the example below, both approaches visit every single node in a Binary Search Tree (BST) and log their values in ascending order.

‍

‍

The recursive version directly mirrors the structure of the tree. It visits the left node, then the current node, then the right node. So, each value gets logged in ascending order.

The version using the while loop does the same thing, but it needs to manually manage its own stack to keep track of where it is in the tree. Looks complicated!

Even if you’re new to BSTs, you can probably see that recursion is much simpler to read and reason about in this case.

Common Mistakes

Let’s face it, recursion is tricky to wrap your head around at first. That’s why you’re reading this! One great way to understand how it works is simply to grab a whiteboard or even just a pencil and paper, and trace it out step by step, like we did for you above. It can feel tedious, but it’s incredibly helpful when you’re just starting out.

That said, there are also a few common “gotchas” that beginners tend to run into.

Forgetting the base case

Your base case is one of the most important parts of any recursive function. If you forget it, or if it doesn’t behave how you expect it to, you can easily end up with infinite recursion. In other words, your function will keep calling itself over and over again without ever stopping!

This is why it’s always a good idea to start your recursive function by clearly defining the base case before you build out the rest of your logic.

Base cases are tricky because you generally need a solid understanding of what your function is meant to do as a whole before you can decide when it should stop.

For example, in the countdown function above, we knew the goal was to log numbers down to but not including 0. That tells us that, no matter what recursive logic we are about to write to do so, our base case should be if(n === 0) return.

Not changing the input

This goes hand in hand with the importance of having a proper base case. Remember, each recursive call must bring your function closer and closer to the base case, so it eventually knows when to stop running. That means the input passed into each recursive call has to change in a way that moves you toward the stopping condition.

In our countdown example, we did this by decrementing n by 1 on each recursive call, countdown(n - 1)

If we didn’t decrement n every time, the base case (if (n === 0) return;) would never be reached…The function would keep calling itself forever! This will inevitably lead to what’s known as “stack overflow”.

Stack overflow

Remember, every time a recursive function invokes itself, a new execution context opens up and a stack frame gets pushed onto the call stack. Each frame stores that function’s local variables, parameters, and its position in the program.

The call stack has a limited size. So, if your recursive calls keep stacking up without ever reaching a base case, the call stack will eventually run out of space. That’s when JavaScript throws an error known as a “stack overflow”.

In other words, you can think of the call stack like a stack of plates:

• Each new function invocation adds another plate to the top.
  
  
• When the function returns, that plate gets removed from the top.
  
  
• But if you keep adding plates without removing any, the stack eventually topples over.

‍

Mixing up return values

It’s easy to lose track of returned values as you tackle a recursive challenge. Often, using your console.log to track exactly what is happening on each call is a fantastic way to confirm that your function is behaving how you expect. In the example below, a console.log(s) has been added to our workflow to track the value of “s” on each new function invocation.

‍

‍

Start practicing recursion

Recursion is an excellent strategy for solving problems that can be broken down into smaller, self-similar subproblems.  It is particularly useful for things like traversing Binary Search Trees, parsing JSON, and navigating file systems.

Remember, while recursion can simplify logic, it generally uses more memory than a loop because each recursive call adds a new stack frame to the call stack. That’s why a simple for…loop is sometimes a better choice when efficiency matters, even though the logic might be more complex.

If you’re new to recursion (which you probably are or you wouldn’t be reading this article!) start small with simple recursive challenges like the ones above. Remember, you don’t need to set up a heavy IDE (Integrated Development Environment) like VS Code to get started either! Check out CSX, Codesmith’s free online learning platform. It includes a full section on recursion with its own built-in coding environment and solution videos. That way you can code along as you go with no setup required. Once you’ve completed CSX’s section on recursion, you can take your practice even further using Codesmith’s CSBin on recursion.

Finally, don’t forget to join Codesmith’s CSX Slack workspace to connect with other engineers, ask for help when you get stuck, and stay up to date on all of our free weekly events!