An Introduction to Recursion

Have you ever heard of recursion? Perhaps you’re new to computer science? Or maybe someone tried to explain it to you but it didn’t make sense? Today we’re going to go through the basics of recursion and walk through an example.

A little story

Imagine you were wrongly accused, convicted, and sent to prison. You know you don’t deserve to be in prison and so you’re planning your escape.

You’re digging a tunnel and you know where to dig, but you don’t know how far the tunnel will have to go exactly.

Based on what you do know, it is feasible, you just have no way to know exactly how far you’ve got left.

You start digging.

How do you know when you’re done?

You might be able to estimate how far it is, how fast you dig, how long you can dig per day, etc.

What if, instead, you just dig and dig and dig until you’re out?

That’s recursion.

Recursion is a way to solve a problem when you don’t know when to stop until you do. That’s a little confusing, so read it over a few more times.

So in our example, when you’ve escaped, you’ll know that you’ve escaped, and then you should stop digging.

That sounds too simple to be helpful, right? Obviously, that’s what you have to do. Stay with me.

So here is some JavaScript to summarize our plan. Focus on the structure (not the triviality of the code)

// will return a Boolean for whether you've escaped
function haveEscaped() {
  // you'll know if you've escaped when you've escaped
}
function dig() {
  // base case
  if (haveEscaped()) {
    // no more digging -> RUN!
  } else {
    dig();
  }
}

You may have realized that the function, dig, calls itself…. well, that’s …weird…?

Isn’t that an infinite loop?? 😱😱😱

Good catch! Often, when working on solving a problem recursively, people run into infinite loops.

Why this is NOT an Infinite Loop

We have a base case, where we check if we’ve escaped, and if so, then we need to run away. When we reach this case, we stop digging. We don’t call dig anymore.

The base case prevents the infinite loop as long as it’s eventually reached. We dig until we’re out, but then we stop.

Otherwise, we just keep digging.

So to recap, it’s extremely important to ensure that you will satisfy your base case.

Unless you’re Hector Zeroni

More formally

So a little more formally, in computer science, recursion is generally defined as:

a function that calls itself continually until it eventually satisfies a base case.

Now let’s work through a real example.

WHAT THE FACTORIAL

TRIGGER WARNING: MATH-Y DEFINITION

Remember factorials? We complained about seeing x and y in math and then they showed us !… great.

Luckily, factorials aren’t so bad. Let’s get the math-y definition out of the way:

the product of an integer and all the integers below it

A product is when you multiply numbers together.

4 * 7 = 28

28 is a product.

An integer is a positive, whole number, like 7 (but not 1.3, or -5).

So a factorial is when you multiply the positive whole number by all the positive whole numbers below it.

3! = 3 * 2 * 1 = 6

5! = 5 * 4 * 3 * 2 * 1 = 120

1! = 1

The only tricky one is:

0! = 1 (feel free to just take my word for it, but more on that here, in case you’re not convinced)

So given an integer, n, the factorial can be represented as:

n! = n * (n - 1) * (n - 2) * (n - 3) ... * 1

How could we solve this using a regular old for loop?

function factorial(n) {
  let result = 1;
  for (let i = n; i > 0; i--) {
    result *= i;
  }
  return result;
}
factorial(3) // 6

Factorial is a common function to show recursively because it’s relatively simple to implement:

function factorial(n) {
  if (n === 0) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}
factorial(4) // 24

Our base case (“when we stop digging”) is when n === 0 because we know we only use positive whole numbers for factorials. Otherwise, we return n * factorial(n — 1).

It’s important to note that we then call factorial(n — 1), not factorial(n) — which would also be an infinite loop. Every time we successively call the function, we should be getting closer to reaching the base case.

Notice how close our recursive implementation matches the mathematical formula for factorial:

if 0 -> 1
otherwise -> n * (n-1)!
n * (n - 1) * ((n-1) - 1) * (((n - 1) - 1) - 1) ... * 1

Some Considerations

Recursion is generally more declarative than alternative approaches: you are focusing on telling the computer what to do rather than how to do it (for loops are imperative — focused on how — by contrast).

This can lead to better code readability (after you’re past the recursion learning curve) but can be at the price of performance.

In languages like JavaScript that don’t implement tail-call optimization, the stack can overflow. You can simulate tail-call optimization with the use of trampolines which can fix this performance issue.

Directing you to StackOverflow to learn about stack overflows 😂

When working with trees, recursion is probably a good candidate. Also, a lot of mathematical functions fit nicely in recursive implementations. Factorial works, as does the Fibonacci sequence.

Conclusion

Recursion sounds scary to many people when first being introduced, and often, for a while, it will feel confusing. But here are the basic steps to solve a problem recursively:

1. Identify the base case. How will you know you’re done?
2. Otherwise, call the function you’re in, passing in a slightly “smaller” parameter (an array with fewer items, a number closer to reaching your base case, a subtree, etc)

Resources

• Colt Steele’s JavaScript Algorithms and Data Structures Masterclass
• MPJ’s Fun Fun Function video on Recursion
• The Shawshank Redemption for inspiration on the digging example
• Why 0! = 1 by Khan Academy
• Thumbnail provided by Free Vector Graphics by Vecteezy

Thanks for reading. If you found value in this, I’d really appreciate it if you recommend this post (by clicking the clap button) so other people can see it!