Factorial Function

'''
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))