Week 7- Recursion

Basically, recursion is used to solve larger problems by breaking those large problems into smaller subproblems until you can manage to handle them. Recursive functions call themselves.

There are 3 main rules for recursion:

1. A recursive algorithm must have a base case.
2. A recursive algorithm must change its state and move toward the base case.
3. A recursive algorithm must call itself, recursively.

Recursion is used in this example and the base case is the first if statement where n is equal to 0 which means that it is the most 'basic' case(rule #1). If we type factorial(0) in the python shell it will just return 0 without doing any recursion.

For the second and third rule to be applied there should be a change of state, which means that we should go on to the next step (else part). Else part of the function says; return n * factorial(n - 1), thus it calls the function factorial again to solve it. If we take n = 3 and type factorial(3) in the python shell, the else part of the code will be executed since n is not equal to 0, therefore factorial(3) = 3 * factorial(2) and factorial(2) =  2 * factorial(1) and factorial(1) = 1 * factorial(0) and factorial(0) = 1(moving from complex problems to smaller subproblems, moving to the base case). So factorial(1) = 1 and factorial(2) is 2, therefore factorial(3) = 3 * 2 = 6. So here, the function calls itself recursively to reach the base case. 

In conclusion recursion makes programmers life simpler. Although it is hard to understand, a programmer should learn how to use it to save his/her time.