# 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

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

```