loading...
Cover image for Recursion Explained (with Examples)

Recursion Explained (with Examples)

christinamcmahon profile image Christina Updated on ・4 min read

“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:
anatomy of recursive solution to Fibonacci problem

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.

Posted on by:

christinamcmahon profile

Christina

@christinamcmahon

Full Stack Web Developer - Feel free to contact me via LinkedIn or connect on Github, I am always happy to chat with folks from this community!

Discussion

markdown guide
 

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.

 

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

 

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?"

 

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...

 

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.

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

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

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!

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

 

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;
}

 

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

 

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

 

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!