```
WEEK10: sorting, start recursion
---------------------------------------------------------------
F: merge sort demo, merge() function, start recursion

QUIZ 5....

MERGE SORT:

- here's a picture of a merge sort:
http://en.wikipedia.org/wiki/File:Merge_sort_algorithm_diagram.svg

- see how it breaks the original problem into two smaller
problems? But the smaller problems can be solved the exact
same way, so why not call the original function to solve
the two smaller problems???

- this is recursion: a function breaks the problem into smaller
problems, and calls itself to solve these smaller problems

- also see how breaking the problem into smaller problems is always
getting you closer to the base case

MERGE function:

- let's start by writing one piece of the mergeSort algorithm:
given two sorted lists, merge them into one fully-sorted list

- suppose we have 3 lists: two that are sorted and one that has
enough space for the other two:

L1 = [2,6,9,15]
L2 = [3,4,5,20]
L3 = [0,0,0,0,0,0,0,0]

(it doesn't matter what's in L3, as long as there's enough room
for L1 and L2 in L3)

- can you write a function to merge the lists L1 and L2 back
into L3, like this?

L3 = [2,3,4,5,6,9,15,20]

This is actually the hardest part of mergeSort -- writing the
merge() function. Once we have this, we can easily write our
mergeSort() function...

RECURSION:

- the python built-in sort uses a divide-and-conquer algorithm,
but before we can learn that algorithm we need to understand
recursive functions: a function that calls itself is recursive

- recursion is most useful when, to solve a problem, you break
the original problem into smaller pieces, but can apply the
same algorithm to the smaller pieces

- a great example is binary search and the number guessing game:

* i'm thinking of a number between 1 and 1000

* if you guess 500, and are told that's not it, but the
answer is less than 500, then you can apply the same
strategy to a smaller problem (i'm thinking of a number
between 1 and 500...you guess 250)

- two things you need to use recursion:

1. a base case, or some way to stop the recursion
2. all chains of recursion need to lead to the base case

for example, in the binary search guessing game, the base case
is when you guess the correct number, and all guesses lead to
smaller and smaller ranges of numbers that contain the base
case (the correct number)

FACTORIAL EXAMPLE:

- the factorial function is defined as follows:

n! = 1 if n=0, and n*((n-1)!) if n > 0

so 0! = 1
1! = 1 * 0! = 1 * 1 = 1
2! = 2 * 1! = 2
3! = 3 * 2! = 6
and so on

You can try this out in python:

>>> from math import *
>>> factorial(3)
6
>>> factorial(4)
24
>>> factorial(5)
120

And the above definition is easily expressed using recursion.

What is the base case??    n = 0
How do we get to a smaller-sized problem??  n! = n * (n-1)!

Will this work???

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

```