Recursion / Recursive Functions

A recursive function is a function which calls itself.

It sounds like a simple concept, but in practice it can be hard to get your head around.

Here’s a lovely example of a recursive function:

void ExplainRecursion () {  
    var explained = GetInput(“Do you understand recursion yet?”);  
    if (!explained) {    
        ExplainRecursion();  
    }
}

It’s particularly nice because it uses recursion to explain recursion. It calls itself — it’s a recursive function. Every time it calls itself, it asks the question “Has recursion been explained yet?” and if the answer is No it calls itself again. It keeps calling itself repeatedly until recursion is finally understood, at which point it quits. What might not be immediately obvious is that when it quits, it will still be inside the previous call, and will keep returning until it reaches the first time it was called. Like this:

ExplainRecursion()

— –>Do you understand recursion yet?

— –>No => ExplainRecursion()

— — — ->Do you understand recursion yet?

— — — ->No => ExplainRecursion()

— — — — →Do you understand recursion yet?

— — — — →No => ExplainRecursion()

— — — — — — –>Do you understand recursion yet?

— — — — — — –>Yes! => Exit function

— — — — →Exit function

— — — ->Exit function

— –>Exit function

Exit function

It’s true that this is a slightly jokey example. It works if you see the source code, but if you only ever saw the output you wouldn’t learn much about recursion. You’d just be asked the same question repeatedly and probably get a bit angry.

Here’s another simple example:

void Factorial(int n) {
    if (n == 1) {
        return 1;
    } else {
        return n * Factorial(n-1);
    }
}

This function is calculating “n factorial”, which is written as “n!” in mathematical notation. In case you’ve forgotten or haven’t come across this concept before, it’s easiest to explain with a concrete example: 5! (“five factorial”) is a quick way of writing 5 x 4 x 3 x 2 x 1. So n! means take the number n and multiply it by all the whole positive numbers that lie between itself and zero.

The above function calls itself, which means that unless n is 1 (because 1 factorial just equals 1), it will return a result… to itself.

Don’t worry if you’re feeling lost already. It took me a long time to be able to look at recursive functions without getting an instant headache. I found it helpful to draw little diagrams. For instance, if we use the above function to calculate 5 factorial.

Remember, the answer we expect is 5 x 4 x 3 x 2 x 1.

The first time we enter the function, we call Factorial(5), so n = 5. The function returns 5 x Factorial(4), so it gets called again and this time n = 4. That returns 4 x Factorial(3), which returns 3 x Factorial(2), which returns 2 x Factorial(1). Factorial(1) just returns 1. Here’s a diagram to help:

Factorial(5) = 5 x Factorial(4)

— –>Factorial(4) = 4 x Factorial(3)

— — — ->Factorial(3) = 3 x Factorial(2)

— — — — →Factorial(2) = 2 x Factorial(1)

— — — — — — –>Factorial(1) = 1

— — — — →= 2 x 1

— — — ->= 3 x (2 x 1)

— –>= 4 x (3 x (2 x 1))

= 5 x (4 x (3 x (2 x 1)))

Normally when a function returns a value, it’s over. We can move on. But with a recursive function, we might just land back inside ourselves again, and then we might return a value to yet another version of ourselves. With complex functions, this can be hard to trace through in your head without losing track. It’s also horribly easy to get stuck in an infinite loop.