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??