What recursion is, how it works under the hood, and why it’s different from loops The three essential parts of any recursive function and how to avoid common pitfalls like infinite loops and stack overflow Real-world use cases where recursion shines, from binary trees to parsing JSON and exploring file systems
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.
The three core parts of a recursive function What’s really happening under the hood in a recursive function Common pitfalls when building a recursive function Where to get started building with 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: 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.
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!”
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.
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.
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.
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.
The function countdown(n) is first defined and stored in global memory. Nothing is on the call stack yet (aside from our Global Execution Context). The function is invoked, passing the number 3 in as the argument - countdown(3). countdown(3) is pushed onto the call stack and gets its own local execution context.
Local memory stores n: 3 (also known as pairing arguments with parameters) Base case (n === 0) fails, so we console.log(3), then prepare to call countdown(2) A new frame for countdown(2) is pushed to the top of the call stack and another local execution context opens up.
The base case (n === 0) fails again. So, we console.log(2), then prepare to call countdown(1). countdown(1) is pushed on top of the stack and yet another local execution context opens. The base case (n === 0) still fails, so we console.log(1) then prepare to call countdown(0).
countdown(0) is pushed to the top of the callstack and another new execution context opens. Our base case (n === 0) finally passes, so we immediately return without logging.
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. Control returns to the suspended countdown(1) frame after its recursive call. With its recursive call complete, countdown(1) also now finishes.
This execution context will now close, get garbage collected, and its frame will pop off the top of the callstack. Control returns to countdown(2) now that its recursive call is complete. Control returns to countdown(3) now that its recursive call is complete.
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.
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.
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.
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.
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”.
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.
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.
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.
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!