# More Practice on Recursion (Optional)
One of the basic examples of recursion is a factorial.

The factorial of a number, denoted as n!, is the product of all possible numbers from 1 up to that number. It is defined as follows:

n! = 1 x 2 x 3 .....x n

For example, 5! (read as "5 factorial"), is 120, because 5! = 5 × 4 × 3 × 2 × 1.

Now that we've refreshed our understanding of factorials, let's attempt to write a function that calculates the factorial of any given number. Write this function based on what you've learned so far. we will explain how can we implement it using recursion later.

Please take 5 minutes to work on this with the person sitting next to you. We'll discuss it as a group afterward.

Here are a few guiding questions:

- What do you want the function to take in?
- What do you want the function to return?
- How can you leverage your knowledge of for loops to implement this function?

To check if your function is working correctly, test it by passing in different numbers and see if you receive the expected outcomes.

Here is the Colab [Link](https://colab.research.google.com/drive/1s3Xe-LkeIvr7p3Mcpq4Z0cmM9hTcHQEe). Please make a copy!

<details>
<summary> <B>Think, then click</B> </summary>

- We want the function to take in a number and return the factorial of that number.
- We are going to use a for loop to iterate over all the positive numbers from 1 up to, and including, that number.
- We are going to use a variable to store the factorial of that number.

def factorial(num):
    total = 1
    for i in range(1, num+1):
      total *= i  
    return total 

Notice that our range starts at 1 and not 0. What do you think would happen if we started our range at 0 instead?
</details>
<br>

### Recursive implementation
**Fun fact:** Every function that uses for loops can be rewritten using recursion, and vice versa.

Now, let's try to implement this function using recursion. This means we'll avoid using for loops, and instead, the function will call itself.

Here's how the recursive function would look.

def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n - 1)

#### Explaining the code
To understand this recursive function, let's call it with an argument of 3:

factorial(3)

We first go through the if statement and check if 3 is equal to zero or 1. In this case, our if statement fails, and we move on to the else statement, which returns:

3 * factorial(3-1)

This will cause the function to call itself, but this time with a value of 2. We then check if 2 is equal to one or zero. Again, the if-statement fails, and the function recursively calls itself with an argument of 1 this time.

2 * factorial(2-1)

With an argument of 1, the function directly returns 1 because it satisfies our base condition (if n == 0 or n == 1).

Let's break down the calls:

factorial(3)            # 1st call with 3
3 * factorial(2)        # Result of 1st call
3 * 2 * factorial(1)    # 2nd call with 2
3 * 2 * 1               # Result of 2nd call as n=1
3 * 2                   # Accumulated product
6                       # Final result

The order that it is returned is a little tricky. Imagine recursion as a series of nested function calls. The innermost function completes and returns first, and then the process moves outward to the next layer, and so on.

factorial(1) => returns 1                 => 1
factorial(2) => returns 2 * factorial(1)  => 2 * 1 = 2
factorial(3) => returns 3 * factorial(2)  => 3 * 2 * 1 = 6