WEEK10: recursion --------------------------------------------------------------- W: recursion in graphics, binary search

Here are some interesting examples of recursion in graphics:

BINARY SEARCH with RECURSION: - the binary search algorithm is a divide-and-conquer algorithm, and these are usually easy to express using recursion: [ 2, 6, 9, 20, 21, 33, 49, 72, 74, 99, 106] ^ ^ ^ low mid high if what we're looking for is at the mid position, we're done elif what we're looking for is less than what's at the mid position do the binary search again with high=mid-1 else (what we're looking for is greater than what's at the mid position) do the binary search again with low=mid+1 and we keep doing this until either we find what we want or high ends up being less than low - here are two ways to express this in python: def recbinsearch(x, y, low, high): """ return True if x is in y """ if high < low: return False else: mid = (low + high) / 2 if x == y[mid]: return True elif x < y[mid]: return recbinsearch(x,y,low,mid-1) else: return recbinsearch(x,y,mid+1,high) #################################################### def recbinsearch(x, y): """ return True if x is in y """ if len(y) <= 0: return False else: low = 0 high = len(y)-1 mid = (low + high) / 2 if x == y[mid]: return True elif x < y[mid]: return recbinsearch(x,y[:mid]) else: return recbinsearch(x,y[(mid+1):]) - what is the difference between these two functions? - do they both work? - why might one be slower than the other??