4. Factorials

The following code shows a recursive method for calculating factorials:

// Calculate the factorial recursively.
private long RecursiveFactorial(long number)
{
    checked
    {
        if (number <= 1) return 1;
        return number * RecursiveFactorial(number - 1);
    }
}

This method first checks whether number is less than or equal to 1. If number ≤ 1, the method returns 1. If number is greater than 1, the method calls itself recursively to calculate (number – 1)! and then returns number times (number – 1)!.

The following code shows a non-recursive method for calculating factorials:

// Calculate the factorial non-recursively.
private long NonRecursiveFactorial(long number)
{
    checked
    {
        long total = 1;
        for (long i = 2; i <= number; i++) total *= i;
        return total;
    }
}

This method initializes the total variable to 1. It then enters a loop where it multiples total by the values between 2 and number. The result is 1 × 2 × 3 × ... × number, which is the factorial.

Some recursive programs may have very large depths of recursion where the method calls itself so many times that the stack memory is exhausted and the program crashes. For example, if a program tried to calculate RecursiveFactorial(1000000), the method would call itself 1 million times. That could exhaust the program's stack space and crash the program.

Fortunately (or unfortunately, depending on how you look at it), the factorial function grows extremely quickly, so the number of recursive calls that will work is limited. These methods use 64-bit long integers to perform their calculations, so they can only hold values up to 9,223,372,036,854,775,807. The value 20! is 2,432,902,008,176,640,000 and the value 21! is too big to fit in a 64-bit integer, so the program can only calculate values up to 20! anyway. That means the recursive version can use, at most, 20 levels of recursion, and the program will never exhaust its stack space.

In general, non-recursive versions of methods are often better than recursive versions because they don't make as many demands on stack memory, but in this example the difference doesn't really matter. The limiting factor for this program is the fact that the factorial method grows so quickly that it can exceed the limits of 64-bit integers.

That brings us to the most important lesson in this example. By default, C# does not check integer operations for overflow. If the result of an integer operation is too big to fit inside the appropriate data type, the program normally does not notice. Instead, it continues merrily along using whatever garbage is present in its variables as if nothing was wrong.

You can force C# to check for integer overflow by placing risky statements inside a checked block, as shown in preceding code. If you omit the checked statements, the factorial methods will try to calculate values for numbers greater than 20. For example, they will report that 21! is -4,249,290,049,419,214,848, which is clearly wrong because it's a negative  number. If you try to calculate factorials for much larger values such as 10,000 or 1 million, the program will exhaust its stack space.

C# ignores integer overflow for performance reasons, although in my tests, using a checked block only increased runtime by about 10%. The moral of all this is that if a certain calculation may cause an integer overflow, then you should place it inside a checked block.

Download the Factorials example solution to see additional details.