'''
This program is an example of recursion. Recursion is essentially a function
similarly calling itself without returning a concrete value until a base case is
met. In this case, the factorial function relies on the base case 1.
n-factorial (n!) is n multiplied by all the numbers between n and 0:
n! = n * (n-1) * (n-2) * (n-3) * ... * 2 * 1
ex. 5! = 5 * 4 * 3 * 2 * [1] <-- base case
This factorial function takes a number n and, if that number is greater than one,
returns that number times the value of the function evaluated at n-1.
Here's an example:
1.
factorial(5):
return 5 * factorial(4) <-- since you are returning the value of something
that has not been evaluated yet, the state of
the first function call is frozen until it is
resolved, whenever that may be. also, step 2
starts here.
2.
factorial(4):
return 4 * factorial(3) <-- step 3
3.
factorial(3):
return 3 * factorial(2) <-- step 4
4. factorial(2):
return 2 * factorial(1) <-- step 5
5. factorial(1):
return 1 <-- base case, since if you multiply everything by 0, it's all 0.
since this returns an actual value, all the values of the function
calls can be calculated.
so, here's the chain of events:
5 * factorial(4) * factorial(3) * factorial(2) * factorial(1) = 1
Since we (and the computer) now know that the last call to factorial = 1, it can
step back through the recursive sequence and unfreeze the state of each function
along the way:
5 * factorial(4) * factorial(3) * factorial(2) * 1
5 * factorial(4) * factorial(3) * 2 * 1
5 * factorial(4) * 3 * 2 * 1
5 * 4 * 3 * 2 * 1
120
and we're done.
'''
def factorial(n):
if n > 1:
return n * factorial(n - 1)
else:
return 1
print(factorial(5))
