A Picture is Worth 1,500 Words

Recursion can be tough to understand — especially for new programmers. In its simplest form, a recursive function is one that calls itself. Let me try to explain with an example.

Imagine you go to open your bedroom door and it’s locked. Your three-year-old son pops in from around the corner and lets you know he hid the only key in a box. (“Just like him,” you think.) You’re late for work and you really need to get in the room to get your shirt.

You open the box only to find… more boxes. Boxes inside of boxes. And you don’t know which one has the key! You need to get that shirt soon, so you have to think of a good algorithm to find that key.

There are two main approaches to create an algorithm for this problem: iterative and recursive. Here are both approaches as flow charts:

The first approach uses a while loop. While the pile isn’t empty, grab a box and look through it.

The second way uses recursion. Remember, recursion is where a function calls itself.

Both approaches accomplish the same thing. The main purpose for using the recursive approach is that once you understand it, it can be clearer to read. There is actually no performance benefit to using recursion. The iterative approach with loops can sometimes be faster. But mainly the simplicity of recursion is sometimes preferred.

The Call Stack

Recursive functions use something called “the call stack.” When a program calls a function, that function goes on top of the call stack. This similar to a stack of books. You add things one at a time. Then, when you are ready to take something off, you always take off the top item.

I will show you the call stack in action with the factorial function. factorial(5) is written as 5! and it is defined like this: 5! = 5 * 4 * 3 * 2 * 1. Here is a recursive function to calculate the factorial of a number:

function fact(x) {
    if (x == 1) {
        return 1;
    } else {
        return x * fact(x-1);
    }
}

Now let’s see what happens if you call fact(3) The illustration bellow shows how the stack changes, line by line. The topmost box in the stack tells you what call to fact you’re currently on.

Notice how each call to fact has its own copy of x. This is very important to making recursion work. You can’t access a different function’s copy of x.