Factorial Formula [Microsoft Python Interview Question]

Given a number $n$, write a formula that returns $n!$.

In case you forgot the factorial formula, $n! = n * (n-1) * (n-2) * ..... 2 * 1$.

For example, $5! = 5 * 4 * 3 * 2 * 1 = 120$ so we'd return 120.

Assume is $n$ is a non-negative integer.

p.s. if this problem seems too trivial, try the follow-up Microsoft interview problem Factorial Trailing Zeroes

Here's an iterative solution, that runs through every number 1 to n, and multiplies it to a running answer.

**For extra credit, can you solve this problem recursively? **

Not just at Microsoft, but at other tech companies too, they typically ask you to solve a question using multiple approaches.

Here's our recursive solution:

In case you aren't familiar with recursion, we typically have two elements to a recursive function:

• a base case (which is used to terminate the recursion)
• the recursive call (where we call the function again)

In this specific case, the recursive call is that the $factorial(n) = n * factorial(n-1)$

However, you can see how this would end poorly, because we could keep going and going and going, making $n$ successively smaller till $-infinity$.

That's why we need a base case – something to terminate the recursion.

For this problem, the base case is that $factorial(0) == 1$, which translate into Python is: