knerr cs21 notes...

back to schedule

WEEK10: recursion
---------------------------------------------------------------
 M: more recursive functions

REVERSE A STRING:

 - can you write a recursive function to reverse a string?

$ python revstr.py 
  string: we love computer science
  reversed: ecneics retupmoc evol ew

 Hint: if you have a string, s, and a working recursive revstr 
 function, what will revstr(s[1:]) + s[0] give you??

 What is the base case/stop-the-recursion condition for this one??

def revstr(str):
  """ Use recursion to reverse a given string.  """
  if len(str) <= 1:
    return str
  else:
    return revstr(str[1:]) + str[0]

 and just for fun, here is the non-recursive version:

def NRrevstr(str):
  """ Non-Recursive version """
  rs = ""
  for i in range(len(str)-1, -1, -1):
    rs = rs + str[i]
  return rs

GRAPHICS:

 - can you write a recursive function to draw concentric circles?
   here's how it would be called from main: 

    reccircle(cenpt, size, color, win)

   your function should draw a circle at the given center point,
   with the given size and color, then call itself again with a
   smaller size.

   when should the recursion end? 


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)

So far all of the recursive functions we have looked at could easily be written without recursion. How about the following image? Can you think of ways to create it with and without recursion?