Factorial Calculation in C#

You can find the source code for this algorithm and many more on GitHub.

The Problem

In mathematics, the factorial of a non-negative integer N, denoted by N!, is the product of all positive integers less than or equal to N.

For example:

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

To calculate the factorial of a number we need to know two things:

1. The factorial of 0 is 1. Factorials can be used to calculate the number of ways we can arrange N elements. Five elements can be arranged in 120 different ways. Well, how many ways can we arrange 0 elements? The only way to arrange 0 elements is to not arrange them at all.
2. The factorial of any non-negative integer N can be calculated with the following formula N! = N x (N-1)!. This means that we can calculate the factorial recursively, by multiplying our number N with the factorial of the number N-1. For example, 5! equals 5 x 4!. This is something we can use in the implementation of the algorithm later on.

Designing the Algorithm

There are two approaches to calculating the factorial of the number, the iterative and the recursive solution.

Iterative Algorithm

We know that a factorial is the number of all positive integers from N to 1. So to calculate the factorial of a number with a loop, we can initialize the result variable to 1 and then multiply the numbers from n to 1 by the result variable inside the loop.

public long Factorial(int number)
{
    long result = 1;

    for(int i = n; i >= 1; i--)
        result *= i;

    return result;
}

Recursive Algorithm

Let's get back to the things we know about calculating a factorial. First, we know that 0! = 1. With that we can create a base case for our function since in that case, we know the result already:

public long Factorial(int number)
{
    if (number == 0)
        return 1;
}

The second thing we know about how to calculate a factorial is that N! = N x (N-1)!. This can be our recursive case:

public long Factorial(int number)
{
    if (number == 0)
        return 1;

    return n * Factorial(n-1);
}

Analyzing the Algorithm

We are now going to calculate the time complexity of the iterative and recursive solutions.

Iterative Solution

Computing the factorial of a number can be performed in a basic "one-pass" style. We multiply the result value with every number from N to 1, in order.

Each time we encounter a new number, we update the result by multiplying it with the number. In this way, we do constant work per element for a total running time of O(N).

Recursive Solution

Computing the factorial of a number, using the recursive solution, can again be performed in a basic "one-pass" style. We get our current number N and call the Factorial() method to N-1.

In this way, we once again do constant work per element for a total running time of O(N).

Conclusion

The factorial is a pretty important operator, used extensively in statistics and probabilities.

In this post, we have discussed how to calculate factorial using an iterative and a recursive algorithm and calculated the time complexity of each approach.

Hope you liked it, and see you again in the next iteration of the C# Algorithms series.