A Simplified Guide to Understanding Recursion

For many beginning computer science students, the idea of recursion is difficult to grasp. I wager that some more experienced computer science students or even some seasoned developers out of college and already out in the field don't really grasp the idea of recursion. As an FYI, I use "function" and "method" interchangeably to mean the same thing (it depends on which language you're most comfy with).

First of all, all recursive functions have what is known as a "base case". A base case is the "state" which you want to get to with the recursive function. If you haven't met the base case yet, you take steps to get to that base case.

As an example to illustrate this concept, let's look at the factorial function. For a technical definition of a factorial, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. In case you forgot about 0! (the ! sign is the formal operator for the factorial), 0! is equal to 1 (so we will just forget about it). Now, let's use 5! as our example. If we were to multiply this out manually, we have:

5! = 5 * 4 * 3 * 2 * 1 = 120

Now that we know this, let's build a recursive function to do this. In this demo, I will use C# as the programming language, but it's the same idea in Java and C++.

public int recursiveFactorial(int base, int multiplier) {
     //this is our base case
     if (multiplier == 1) {
         return base;
     }
     else {
         //if we haven't met our base case yet, we take steps to get to that base case
         base = base * multiplier;
         return recursiveFactorial(base, (multiplier - 1));
}

Now let's look at what this function does. It first takes in 2 integers as input, base and multiplier. Base is the number we start out with (in this case, 5), and multiplier is the number we will multiply base by if we haven't met our base case (multiplier starts out as base - 1 to fit the definition of the factorial). The base case here is to get multiplier = 1. So now, let's run our function and see how the recursion works.

First, we will call:

recursiveFactorial(5, 4);

Now here, we check: is 4 equal to 1? No, it is not, so the else part of our recursive function activates and we simplify things to get closer to our base case by calling the function again with 20 as our base input variable and (4-1) as our multiplier input variable.

recursiveFactorial(20, 3);

Now we check again: is 3 equal to 1? No, it is not, so the else part of our recursive function activates again (and we multiply base times multiplier) to get closer to our base case.

recursiveFactorial(60, 2);

Are we starting to get the picture yet? Now here, we check: is 2 equal to 1? No, it is not, so the else part of our recursive function activates yet again and things are simplified even more (by multiplying base times multiplier again) to get ever closer to our base case.

recursiveFactorial(120, 1);

We check again: is 1 equal 1? Yes, we have finally met our base case, so we just end things by returning base. From here, the value "bubbles up" to the top "level" (where we first called the recursiveFactorial function).

If you've ever heard the term "stack overflow", it comes from this idea of recursion. With a stack overflow, a recursive function is called so many times that the computer doesn't have enough memory available to handle the recursion, so the computer crashes.

So does this guide help you to grasp the idea of recursion? If you are a seasoned developer, can I improve this guide (or give better examples)? Please let me know in the comments below.