CS21 Lab 11: Recursion

Due SUNDAY night, Dec 9

Make sure all programs are saved to your cs21/labs/11 directory. Files outside this directory will not be graded.

$ update21
$ cd ~/cs21/labs/11

CS21 Lab 11: Recursion

Recursive functions to write

For this lab, write each function below recursively, then test in main (so all your functions will be in the same file). The more you practice, the easier recursion gets! Use the provided starter code recursion.py that contains function stubs. We may have written some of these in class. Also, make sure you could write iterative (using loops) as well as recursive (no loops!) versions of each.

1) sum a list

Function should recursively sum all items in a given list and return the sum. For example: rsum([1,2,3,4,5]) should return 15, and rsum([]) should return 0. Obviously, no using the built-in sum() function!

2) max of a list

Function should recursively find the largest item in the list and return it. For example: rmax([5,20,-4,18]) should return 20. Obviously, no using the built-in max() function!

3) reverse a string

Function should return the reverse of a given string. For example: rrevStr("hello") should return “olleh”.

4) blastoff

Function should count down (print one number per line) from the given start number to 1, then print “blastoff!”. For example, rblastoff(10) should count down from 10 to 1, then print “blastoff!”.

5) get divisible by 3

Function (rgetMod()) should ask the user to enter an integer that is divisible by 3. Assume the user will enter an integer. If given invalid input (not divisible by 3), should keep asking.

6) xerox

Function (rxerox(item,n)) should generate and return a python list containing n copies of the item. For example, rxerox("paper", 4) should return ['paper', 'paper', 'paper', 'paper'], and rxerox(2, 10) should return [2, 2, 2, 2, 2, 2, 2, 2, 2, 2].

7) raise to power

Function rraise(n,m) returns n raised to the mth power. For example, calling rraise(6,2) returns 36.

8) is palindrome?

Function risPalindrome(text) returns True if given text is a palindrome (same forwards and backwards). For example, risPalindrome("HANNAH") should return True.

9) is sorted?

Function risSorted(L) returns True if given list is in-order. For example, risSorted([1,2,3,4,5]) should return True.

10) in list?

Function rinList(x,L) returns True if x is in the list L. For example, rinList("x", list("abcdefg")) should return False.

11) coin flips

Function rcoinFlip(n) flips a coin n times, and returns the total number of Heads. For example, rcoinFlip(100) might return 50 (or 49, or 51, etc).

12) count in list

Function rcount(x,L) returns how many times x is in the list L. For example, rcount("a", list("aardvark")) should return 3.

Testing your functions

You should always test your code! assert() statements are a great way to do that (although not all of the above functions will work with asserts). For each function you write, add some test calls to main() to make sure it works for all cases you can think of. If using asserts, no output means the assert test passed. If the assert test doesn’t pass, you will see an AssertionError. Here are a few example tests:

python3
assert(rsum([1,2,3,4,5])==15)
assert(rsum([])==0)
assert(rsum([100])==100)

assert(rmax([1,2,3,4,5])==5)
assert(rmax([100])==100)
assert(rmax([5,4,3,2,1])==5)

assert(rrevStr("hello")=="olleh")
assert(rrevStr("A")=="A")
assert(rrevStr("")=="")
assert(rrevStr("HANNAH")=="HANNAH")

Submit

Once you are satisfied with your programs, fill out the questionnaire in QUESTIONS-11.txt. Then run handin21 a final time to make sure we have access to the most recent versions of your file.