Software Engineer · Teacher · Author · Vegan

Ah, recursion, one of those intimidating programming topics that make many developers’ heads spin 🤯 . These types of problems can be difficult to conceptualize, especially when you’re under pressure during an interview. I know I’ve felt that before! Well, that’s why I am writing this blog post series on recursion, to help you and me learn it better. As I’ve spent more time learning about it, I’ve come to find it a fascinating topic and appreciate how elegantly you can use it to solve certain types of problems.

Here are the other posts in this series if you haven’t checked those out yet:

- The Obligatory Factorial Function
- Sum an Array of Numbers 3 Ways
- Flattening Arrays
- Palindromes
- Revisiting the Factorial Function with Tail Recursion

For the first post in this series on recursion, we are going to look at what recursion is and walk through the “Hello World” of recursion.

So what is recursion? Recursion occurs when a function keeps calling itself until some condition is met. This condition is often referred to as the base case. Without the base case, the function would never stop calling itself resulting in what’s known as a stack overflow error. The base case is really important and returns a value to end the recursive process.

Let’s look at an example. The “Hello World” of recursion is a factorial function, so let’s start with that.

In math, the factorial of a positive integer `n`

, denoted by `n!`

, is the product of all positive integers less than or equal to `n`

. For example, 5 factorial, denoted as `5!`

, is `5 x 4 x 3 x 2 x 1`

which equals 120. It’s also worth noting that `0!`

is 1.

We can write a factorial function using a `for`

loop as such:

```
function factorial(n) {
let product = 1;
for (let i = n; i > 0; i--) {
product = product * i;
}
return product;
}
factorial(5); // 120
factorial(1); // 1
factorial(0); // 1
```

The implementation above uses a `for`

loop that iterates from `n`

down to 1, building up the product.

One interesting thing about code written using loops is that they can also be written recursively. In fact, some languages such as Elixir don’t even have looping constructs and rely completely on recursion. Let’s look at what the factorial function looks like when implemented using recursion:

```
function factorial(n) {
if (n === 0) {
return 1;
}
return n * factorial(n - 1);
}
factorial(5); // 120
factorial(1); // 1
factorial(0); // 1
```

In this implementation, the recursion happens in the `else`

block, where the `factorial`

function is calling itself. If we were to expand this call stack out, it would look like this:

```
factorial(5) = 5 * factorial(4)
factorial(5) = 5 * (4 * factorial(3))
factorial(5) = 5 * (4 * (3 * factorial(2)))
factorial(5) = 5 * (4 * (3 * (2 * factorial(1))))
factorial(5) = 5 * (4 * (3 * (2 * (1 * factorial(0)))))
factorial(5) = 5 * (4 * (3 * (2 * (1 * 1))))
```

Here, the base case is when `n === 0`

, in which `factorial`

isn’t called again and `1`

is simply returned. Without this base case, a stack overflow error would occur, which looks like the following in JavaScript:

RangeError: Maximum call stack size exceeded

I hope you found this post useful. This isn’t the most practical application of recursion, but I find it to be a great, basic example to illustrate how recursion works. Stay tuned for the next post in my series on recursion, as we’ll continue to look at more examples and facets of recursion.

*
Disclaimer: Any viewpoints and opinions expressed in this article are those of David Tang and do not reflect those of
my employer or any of my colleagues.
*