What is recursion?

Recursion is a specific way to solve problems. It’s a pretty simple concept once you understand it, but regularly confuses people when they first learn it.

In essence, when solving a problem, there often is a case that is simple to solve, a so-called base case. But many other cases that are complex and require a lot more computation. In recursion we make use of this. We look at the input, if we happen to have the simple case, we can go and return the easy solution. If we happen to have any of the more complex cases, we do the smallest bit of computation to get closer to our simple case, and try again. By doing those simple steps and trying over and over again we eventually reach our simple case that is easy to answer.

There are many problems where this recursive step-wise approach yields smaller and easier to understand code than trying to solve it all at once with loops and local variables.

Factorial, the common example

Recursion is hard to understand from an explanation alone, so let’s code up an actual example.

In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example,

5 ! = 5 × 4 × 3 × 2 × 1 = 120.

The value of 0! is 1, according to the convention for an empty product. wikipedia

Let’s see how we can code this up. First we need our simple case that’s easy to solve. A good base case would be 0! since we know that it’ll return 1:

function factorial(number) {
    if (number == 0) return 1;
}

What do we do for the other cases? We take the current number and multiply it with the factorial of number - 1:

function factorial(number) {
    if (number == 0) return 1;

    return number * factorial(number - 1);
}

Let’s use 5! to step through this function and see if it actually works:

factorial(5) = 5 * factorial(4)
             = 5 * 4 * factorial(3)
             = 5 * 4 * 3 * factorial(2)
             = 5 * 4 * 3 * 2 * factorial(1)
             = 5 * 4 * 3 * 2 * 1 * factorial(0) // Yay, we'll be calling our base case.
             = 5 * 4 * 3 * 2 * 1 * 1
             = 120

By reducing the number by one and calling itself over and over, we eventurally reach our base case.

The greatest common divisor

Let’s look at a more interesting example, calculating the greatest common divisure using Euclid’s algorithm. The formal description of the algorithm is:

gcd(a, 0) = a
gcd(a, b) = gcd(b, a mod b)

So what does that mean? Given a function gcd that takes two arguments, a and b.

  • if b is 0 our solution is a
  • otherwise: try again, but pass b as first argument and a % b as second argument.

In JavaScript this looks like:

function gcd(a, b) {
    if (b == 0) return a;

    return gcd(b, a % b);
}

Let’s step through it again using 54 and 24 as input like in the example on wikipedia:

gcd(54, 24) => gcd(24, 54 % 24)

gcd(24, 6)  => gcd(6, 24 % 6)

gcd(6, 0)   => 6  // Yay, we got to our easy case again.

It might be hard understand when to use a recursive instead of an iterative approach to solve a problem from some toy examples, this takes time and practice using recursion to solve problems. But I hope it made you understand the concept behind recursion a little bit better.