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


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:


def mergeSort(L):
  
  if len(L) > 1:
    half = len(L)/2
    L1 = L[0:half]
    L2 = L[half:]
    mergeSort(L1)
    mergeSort(L2)
    merge(L1,L2,L)



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)