Recursion

Open a nesting doll, and inside you find the same doll, only smaller. Open that one, and there is another. This goes on down to the smallest doll, which no longer opens. Then the dolls are put back together in reverse order: the smallest is closed inside the next one, that one inside the next, and so on up to the largest.

Some problems are built the same way: inside the problem sits the same problem, only smaller. The factorial of a number n is the product of all the whole numbers from 1 to n. It is defined by two rules:

• the factorial of zero is 1;
• the factorial of n is n times the factorial of n - 1.

A C# method repeats this definition word for word by calling itself:

Console.WriteLine(Factorial(5)); // 120

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

A method calling itself is called recursion, and such a method is recursive.

The two parts of a recursive method

A recursive method always has two parts. Let's look at each.

The base case

The branch in which the method ends without a new call is called the base case. In Factorial it is if (n == 0): the call Factorial(0) returns 1 at once. This is the smallest doll, the one that no longer opens.

Without a base case the calls never end. That is why every step of the recursion must bring the argument closer to the base case.

The call to itself

The line return n * Factorial(n - 1); calls the same method with an argument one smaller. Factorial(5) waits for the result of Factorial(4), which waits for Factorial(3), and so on down to Factorial(0).

Then the results travel back up the chain, the way the dolls are put back together:

1. Factorial(0) returns 1.
2. Factorial(1) returns 1 * 1, which is 1.
3. Factorial(2) returns 2 * 1, which is 2.
4. Factorial(3) returns 3 * 2, which is 6.
5. Factorial(4) returns 4 * 6, which is 24.
6. Factorial(5) returns 5 * 24, which is 120.

The call stack

Every call gets its own parameter n, so Factorial(5), Factorial(4) and the other calls don't get in each other's way. Until a call has finished, the runtime keeps a frame for it: its parameters and the place to return the result to.

The frames of unfinished calls lie in a pile called the call stack:

• a new call puts its frame on top;
• a finished call takes the top frame off.

Press "Next step" and watch the pile of frames grow up to Factorial(0) and then come apart from the top down. The widget computes Factorial(3) so that the pile fits on the screen.

The code that follows the recursive call in a method runs only once the nested call returns. That is why the multiplications in Factorial happen in reverse order: 1 * 1 in Factorial(1) comes first, and 5 * 24 in the very first call, Factorial(5), comes last.

Here the doll picture stops working. The dolls are all different, but the program has a single method. Only each call's own data is kept separately: the parameter n and the place to return the result to.

Recursion depth

The call stack is not endless. Every call that has not returned yet takes up room in it, and with recursion that goes too deep the room runs out. Then a StackOverflowException occurs.

Most exceptions can be caught: the program can have code ready that runs instead of stopping, and carry on. A StackOverflowException cannot be caught this way: the program ends at once.

Interviewers often ask: "Can you catch a StackOverflowException?" The answer is no. That is why recursion is written so that its depth is sure to stay small.

A loop instead of recursion

The same factorial can be computed with a loop:

Console.WriteLine(FactorialLoop(5)); // 120

int FactorialLoop(int n)
{
    int result = 1;
    for (int i = 2; i <= n; i++)
    {
        result = result * i;
    }
    return result;
}

The loop calls no new methods: the variables result and i change in place, and the pile of calls does not grow, however many steps there are. When the recursion depth is unknown in advance or may turn out large, you write a loop instead of recursion.

Common mistake

A recursive method was called with an argument from which the base case cannot be reached:

Console.WriteLine(Factorial(-1)); // ✗

Stack overflow.

From -1 the chain goes to -2, -3 and on, and the condition n == 0 never holds. Every call adds a frame to the stack until the room runs out. Then the runtime prints Stack overflow. and ends the program.

Check that the base case can be reached from every valid argument, and reject invalid arguments before the recursive call. For example, check n >= 0 in an if and call Factorial(n) only inside that branch.

Key points

• A recursive method calls itself, and it needs a reachable base case: a branch where it ends without a new call.
• Every call gets its own parameters and waits for the nested call to return; the code after the recursive call runs on the way back.
• Recursion that goes too deep overflows the call stack, and a StackOverflowException cannot be caught: the program ends. When the depth may turn out large, you write a loop.