```
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:

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

```