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


REVIEW: concentric circles solution

def reccircle(p, radius, color, w):
  """ draw recursive circles """
  if radius > 1:
    c = Circle(p, radius)
    c.setOutline(color)
    c.draw(w)
    reccircle(p, radius*0.45, color, w)

RECURSIVE GRAPHICS:

 - how can we use recursion to draw something like this??

Here are some other interesting examples of recursion in graphics:

• letters
• plants
• L-systems
• maze generation
• more plants
• fern demo
• cs recursion projects

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