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)