Getting a Handle on Recursion

Recursion is a concept that is fundamental to programming, and yet there are engineers with Master’s degrees in Computer Science and multiple years of experience who have trouble wrapping their minds around it. Classic textbook examples such as finding the nth number in the Fibonacci sequence are certainly simple and illustrative, but they are also somewhat subtle, and not everyone has an easy time applying them to real-world problems.

So far, I have had little success in helping people with this issue, but recently I stumbled on a recursion sample in the MDN JavaScript documentation that, it seems to me, could be an ideal tool to help programmers wrap their minds around how recursive function calls behave. It doesn’t do anything remotely useful, except to clearly illustrate what happens when a function calls itself repeatedly.

Here is the sample, with only minor adjustments by yours truly:

function recurse(num) {
    if (num < 0)
        return;
    // Do something before the recursive call
    document.getElementById('output').innerHTML += 'Before: ' + num + '<br>';
    // Make the recursive call
    recurse (num - 1);
    // Do something after the recursive call. We won't get here
    // until after the above call to recurse() has exited
    document.getElementById("output").innerHTML += 'After: ' + num + '<br>';
}

recurse(3);

Here is the output:
Before: 3
Before: 2
Before: 1
Before: 0
After: 0
After: 1
After: 2
After: 3

The key to understanding this output is to remember that whenever a function is called, the program execution will not proceed to the next line until the function exits. Let’s walk through it.

First, we call the recurse() function with num = 3. This will produce the output, “Before: 3” and then call recurse() with num = 2.  This will print out “Before: 2” and then call recurse() with num = 1. This will print “Before: 1” and call recurse() with num = 0. Here is where it starts to get interesting: It prints out “Before: 0” and then calls recurse() with num = -1.

Because num < 0, the function simply returns without printing anything. This allows the code that called the function to continue to the next line, which prints “After: 0” and exits. This allows the calling code to continue to the next line and print “After: 1” and exit. And so on.

Here is a short video walk-through:

I’ve also set up a JSFiddle with this same function so that you can play with it yourself and get a feel for it. Once you feel comfortable with that, then it’s time to  take it to the next level with a slightly more complex example on JSFiddle.

If you’re looking for inspiration, you might also enjoy browsing through the discussions of real-world recursion on StackOverflow and Quora.