Recursion

method of breaking up problem into smaller and smaller problems until it can be easily solved
while iterative algorithms use loops, recursive algorithms rely on functions that call themselves
any problem that can be solved iteratively can be solved recursively
- sometimes recursive is more elegant

Three Laws of Recursion

a recursive algorithm must have a base case
a recursive algorithm must change its state and move towards the base case
a recursive algorithm must call itself, recursively

Recursive Algorithm

written inside a function
must have a base case
- a condition that ends a recursive algorithm to stop it from continuing
inside the function, the function calls itself
each time it calls itself it grows closer to the base case
when the base case condition is satisfied the problem is solved and the function stops calling itself

example in Python:

def bottles_of_beer(bob):
    if bob < 1:
        print('No more bottles of beer on the wall. No more bottles of beer.')
        return
    tmp = bob
    bob -= 1
    print('{} bottles of beer on the wall. {} bottles of beer. Take one
            down, pass it around, {} bottles of beer on the wall.'.format(tmp, tmp, bob))
    bottles_of_beer(bob)

if statement satisfies 1st law
bob -= 1 satisfies 2nd law
calling bottles_of_beer(bob) inside bottles_of_beer(bob) satisfies 3rd law

example in Python:
```
def print_to_zero(n):
    if n < 0:
        return
    print(n)
    print_to_zero(n-1)
```
- here the 2nd law is satisfied by the n-1 argument given to the function inside the function