Recursion Explained (with Examples)

“To understand recursion, one must first understand recursion” - Unknown

Recursion is a method of solving problems where you solve smaller portions of the problem until you solve the original, larger problem. A method or function is recursive if it can call itself.

function understandRecursion(doIUnderstandRecursion) {
    const recursionAnswer = confirm('Do you understand recursion?');
    if(recursionAnswer === true) { // base case
        return true;
    }
    understandRecursion(recursionAnswer); // recursive call
}

For the example above, notice the base case and recursive call which make this a recursive algorithm. Recursive functions must have a base case, or a condition in which no recursive call is made. I think the best way to understand recursion is to look at examples so let’s walk through two common recursive problems.

Example 1: Calculating the Factorial of a Number

Calculating the factorial of a number is a common problem that can be solved recursively. As a reminder, a factorial of a number, n, is defined by n! and is the result of multiplying the numbers 1 to n. So, 5! is equal to 5*4*3*2*1, resulting in 120.

Let’s first take a look at an iterative solution:

function factorial(num) {
    let total = 1;
    for(let n = num; n > 1; n--) {
        total *= n;
    }
    return total;
}

The iterative solution above is fine but let’s try rewriting it using recursion. When we think about solving this problem recursively, we need to figure out what our subproblems will be. Let’s break it down:

1. We know factorial(5) = 5 * factorial(4) aka 5! = 5 * 4!.
2. To continue, factorial(5) = 5 * (4 * factorial(3)) which equals 5 * (4 * (3 * factorial(2)) and so on…
3. ...Until you get 5 * 4 * 3 * 2 * 1 and the only remaining subproblem is 1!.
4. factorial(1) and factorial(0) always equals 1 so this will be our base case.

Using this line of thinking, we can write a recursive solution to our factorial problem:

function factorial(n) {
    if(n === 1 || n === 0) { // base case
        return 1;
    }
    return n * factorial(n - 1); // recursive call
}

Example 2: Fibonacci Sequence

Another fun problem that can be solved using recursion is the Fibonacci sequence problem. As a reminder, the Fibonacci sequence is a series of numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on. The pattern involves totaling the two previous numbers so 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, etc. In other words, the Fibonacci number at position n (for n > 2) is the Fibonacci of (n - 1) plus the Fibonacci of (n - 2).

Again, I think it’s helpful to see an iterative solution first:

function fibonacci(n) {
    if(n === 0) return 0;
    if(n === 1) return 1;

    let fibNMinus2 = 0;
    let finNMinus1 = 1;
    let fibN = n;

    for(let i = 2; i <= n; i++) { // n >= 2
        fibN = fibNMinus1 + fibNMinus2; // f(n-1) + f(n-2)
        fibNMinus2 = fibNMinus1;
        fibNMinus1 = fibN;
    }
    return fibN;
}

As you’ll see, the recursive solution looks much simpler:

function fibonacci(n) {
    if(n === 0) return 0; // base case 1
    if(n === 1) return 1; // base case 2

    return fibonacci(n - 1) + fibonacci(n - 2); // recursive call
}

If you were to call fibonacci(5), the following represents the calls that would be made:

Fibonacci with Memoization

I wanted to take this opportunity to mention another approach to this problem, called memoization. Memoization consists of an optimization technique that stores the values of the previous results, similar to a cache, making our recursive solution faster. If you look back at the calls made to compute fibonacci(5) in the image above, you can see that fibonacci(3) was computed twice, so we can store its result so that when we compute it again, we already have it.

Take a look at how our fibonacci solution changes when we add memoization:

function fibonacci(n) {

    const memo = [0, 1]; // cache all computed results here

    const fib = (n) => {

        if(memo[n] != null) return memo[n]; // base case

        return memo[n] = fib(n - 1, memo) + fib(n - 2, memo); // recursive call

    };

        return fib(n);

}

Why Use Recursion?

To be completely frank, a recursive solution is almost always slower than an iterative one. That being said, if you look back at our Fibonacci solutions, the recursive solution is much easier to read plus memoization can help bridge the gap in speed. Recursion is generally easier to understand and usually requires less code.

Conclusion

Now that we’ve gone over some examples, I hope recursion is a little easier for you to grasp and that you can see why we would use it. In a future post, I plan to take a look at the tree data structure which uses recursion in many of its methods so stay tuned! This article only scratches the surface of recursion’s potential so here are a few resources you might find helpful if you want to continue your studies.

• Practice with Recursive Problems via HackerRank
• Famous Recursive Problems via Princeton

Comments

[Aaron McCollum]

Thanks Christina! This helps my understanding of recursion. I'm going through a JS course right now and just came across this for the first time and was like "what?"

[Christina]

It makes me so glad to hear that this helped, best of luck with your studies! I'm curious which JS course you're taking...

[Aaron McCollum]

The JS intro course on freeCodeCamp. I just discovered CodeWars as well, which I'll throw in there to break things up. Near the end of the JavaScript Introduction part of the course and just got into recursion. I have not figured out the solution yet but your article has helped.

[Christina]

Hasn't heard of CodeWars before but I started programming on freeCodeCamp so I'm a big fan of their courses! Good luck!

[Aaron McCollum]

Thanks! Have you made it through their entire course offering? (Before Python's update I mean)

[Christina]

Not yet, only the responsive web design and JS algorithms ones so far. I've taken several other courses through Coursera, Scrimba, and Codecademy though. There are so many excellent, free resources or there!

[Aaron McCollum]

True that! I've done free versions of Codecademy before - that was my first HTML course almost a year ago today. Ah the memories.

[David]

Welcome to the world of programming, Aaron -- I used to hate recursion because it was not intuitive to me at all no matter who explained it. When I learned it there weren't such abundant resources. It took me years to come back around to learning it (all the while hoping no one around me would find out that I couldn't do it)

Here are a few things that may help with some lingering questions (e.g. when to use it?). Whenever you've a problem and the only thing that comes to mind as the answer the problem is to "enumerate" or "try all possibilities" or an "exhaustive search" is usually a signal for recursion, because the recursive parts are probably repetitive...

One thing that I was aware of, but wish someone had really forced me to understand was thinking about how to do recursion in terms of a decision tree aka recursive tree -- "in my current position, what are my options?"

With Fibonacci, we have two branches (i.e. two decisions) at EVERY (node) call with one exception (base case) when the value that comes into our function is 0 or 1

Drawing this out by hand is an exercise that has made it click for me. While I can mostly do this in my head now or in a comment in the code, if I can't determine what my decisions and exceptions are, then I cannot write the code

[Aaron McCollum]

Thanks David! I appreciate this. 😊

[Joshua Baker]

Also, for some algorithms, an iterative solution may not be an option.

Actually, that's false. Anything that can be implemented with recursion can also be implemented with iteration. After all, the CPU doesn't know recursion -- it only knows jump instructions. So every recursive function in a high-level language eventually gets translated into an iterative subroutine.

[Adrian]

The following booklet contains a few problems solved with both recursion and also iterative approach:

codeguppy.com/site/download/recurs...

On the same site you can also explore the following two playgrounds with problems solved with both recursion and iterative approach:

Flood fill
codeguppy.com/code.html?t=flood_fill

Find element in a hierarchical structure
codeguppy.com/code.html?t=find_max

[Christina]

Thanks for pointing that out and for the explanation, totally makes sense! I've gone ahead and taken it out :)

[David]

In fact, what Josh notes is actually what's done in practice most of the time (when possible) and what you've done turning your recursive solution into a "memoized" version. For big company interviews, these types of questions are becoming common-place -- where recursion (already a challenge for some) is the brute force method, but with a large enough input would result in an overflow of the call stack. This optimization that you've done is often known as "dynamic programming" and while Fib is the classic example, there are certainly some problems that require some exceptional thought to convert from standard recursion (much more elegant IMO) to one that's iterative (DP) and you can certainly find tons on Leetcode. I wouldn't worry too much about it unless you're super curious -- took me forever to learn.

There's also one "in-between"/hybrid memoized version -- in "dynamic programming" there are typically two approaches as well: 1) top-down, 2) bottom-up. I wrote a gist (in JS) for a friend trying to understand it a couple months back: the fibIterative is the top-down approach, and the fibOptimal is similar to yours but instead of two well-named variables that you have, I've stuck them in a two-element array/tuple: gist.github.com/wulymammoth/bdb5e3...

[James Carter]

It's good to know you can do all recusive algorithms iteratively also, I had always wondered.
Your example above does not iterate unless you change n > 1 not n < 1, it had me going for a bit you and should always test your code ;-)

function factorial(num) {
let total = 1;
for(let n = num; n > 1; n--) {
total *= n;
}
return total;
}

[Christina]

Oops, thanks for pointing that typo out, I've made the change in the post.

[Shannon Crabill]

I was dreading learning recursion, but this write up helped for it to click.

Thank you!

[Christina]

That makes me so happy to hear since I've been in your shoes too!

[Athul Muralidhar]

i absolutely love recursion! it could be a bit tricky to wrap your head around, but once you get the gist of it, things just are more simpler and elegant

[Christina]

Yes! I love how recursion appears in so many walks of life: programming, math, art, nature, etc. MC Escher is one of my favorite artists due to his use of recursion!