# Factorial

As I am an electrical engineer, who realized that he likes computer science much better than the stuff he learned at university for the last few years, I am in some kind of dilemma… But that is actually not that bad, as I can start to learn new things! :)

I bought a book about algorithms, just because I was confused all the time what
is this \(f(x) = O(g(x))\) stuff all about. I quickly found out, that I
pretty much suck at implementing (not to say understanding) algorithms. So, I
decided to start some "An Algorithm a Day" series as some kind of documentation
for my nightly activities in front of `nvim`

and `atom`

.

Actually "An Algorithm a Day" is a lie, I can’t manage to understand and
implement an algorithm *every* day. First, my girlfriend might kill me. Second,
as I mentioned earlier, I currently suck at implementing algorithms; that’s the
reason I require infinite time to implement something properly. Third, I have
some kind of real life; I love cooking hanging around with friends and so on.
So, dear reader, expect that "An Algorithm a Day" might become "An Algorithm a
Week" or so.

Let’s start with some simple math stuff. I decided to do some computation in Python to get the factorial of a given number. The factorial is defined as such:

That’s pretty easy to implement in Python! Let’s just do it!

```
def factorial(n):
res = 1
for i in range(1, n+1):
res *= i
return res
```

I also found out that this way of solving this problem is the so called
*iterative* way. There is almost always another approach called *recursion*.
We can define the factorial also in a recursive manner:

This means that we devide the problem into several problems of the same type; each distinct problem is simpler to solve as the whole problem. This is continued until the end condition, which in this case is \(n = 0\).

The Python code finally looks like this:

```
def factorial(n):
if n == 0:
return 1
if i > 0:
return n * factorial(n-1)
```

Despite recursive algorithms seem to be the most elegant thing in the world of computing, they IMO suck. You can reach the max. recursion depth rather quickly:

In [1]: f(2134123131) --------------------------------------------------------------------------- RecursionError Traceback (most recent call last) <ipython-input-5-98a27640969b> in <module>() ----> 1 f(2134123131) <ipython-input-4-ce7906f37218> in f(n) 3 return 1 4 if n > 0: ----> 5 return n * f(n-1) 6 7 ... last 1 frames repeated, from the frame below ... <ipython-input-4-ce7906f37218> in f(n) 3 return 1 4 if n > 0: ----> 5 return n * f(n-1) 6 7 RecursionError: maximum recursion depth exceeded in comparison