knerr cs21 notes...

back to schedule

WEEK09: sorting (and more analysis of algorithms)
---------------------------------------------------------------
 F: recursion

HOMEWORK HINTS:

 - treat the zipcodes as strings...see the last paragraph 
   in the lab writeup

 - see /home/jk/inclass/listoflists.py for an example of using
   a list of lists. here's how you would access the y data value
   from the 4th line of the data.txt file:  print data[3][1]


FACTORIAL EXAMPLE:

 - from last time...does this work???

def factorial(n):
  if n == 0:
    return 1
  else:
    return n * factorial(n-1)

 - try running /home/jk/inclass/factorialstack.py to see the stack
   for the recursive factorial function:

$ python factorialstack.py

please enter a positive integer...
           n: 4
-------------------------------
  in factorial...stacknum = 1, n = 4
  calling 4 * factorial(3)
    in factorial...stacknum = 2, n = 3
    calling 3 * factorial(2)
      in factorial...stacknum = 3, n = 2
      calling 2 * factorial(1)
        in factorial...stacknum = 4, n = 1
        calling 1 * factorial(0)
          in factorial...stacknum = 5, n = 0
          returning 1
        returning 1 
      returning 2 
    returning 6 
  returning 24 
factorial(n): 24


GETTING INPUT FROM USER:

 - here's another example that many of you have tried to write:
   (see getLetter.py)

def getLetter():
  """
  Use recursion to get valid input from the user
  """
  letter = raw_input("please enter a letter: ").strip()
  if len(letter)==1 and letter.isalpha():
    return letter
  else:
    print "that's not a letter!!"
    return getLetter()


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