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