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:

- 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. - 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.

## Top comments (0)