CS21 Lab 11: Recursion

This lab will not be graded and has no due date. You should do this lab sometime before the final exam, as practice for the final.

Recursive functions to write

For this lab, just write and test as many of these functions as you can. The more you practice, the easier recursion gets! We may have written some in class. Also, make sure you can write iterative (using loops) as well as recursive (no loops!) versions of each...

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!

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!

reverse a string

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

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!".

get integer input

Function (rgetInteger()) should ask the user for an integer and return the integer. If given invalid input (not an int), should keep asking.

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].

raise to power

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

is palindrome?

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

is sorted?

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

in list?

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

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).

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:

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")

Turning in your labs

Again, we're not grading this one, so you don't have to run handin21. Just make sure the functions all work and pass any tests you wrote.