# moreRecursionPractice.py P. Conrad for CS5nm # Extra Recursion Practice from 11/26/2008 import sys # new_check_expect checks whether a function produces the expected result # consumes: # check: a string containing the function call we want to test # expect: the value we are expecting (typically a literal value) # msg: True if we should print output, False if we should not # default is True) # produces: # True if test passes, False otherwise # side effect: # prints a message indicating whether the test passed or failed def new_check_expect(check,expect,msg=True): if msg: print "Testing " + check + " :", try: actual = eval(check) result = (actual == expect) if msg: if result: print " Passed!" else: print " Failed! Expected: " + str(expect) + " Got: " + str(actual) return result except: if msg: print " ERROR: Unable to evaluate test: " + str(sys.exc_info()[0]) # consumes: # check: an expression to test, as a string # expectedException: the exception you should get in response # msg: whether or not to print results as a side effect # produces: # boolean: True is the test comes out as expected, i.e. you get the # exception that you think you are going to get # side effect: # if msg is True, then print messages about what happened to the console def check_exception(check,expectedException,msg=True): if msg: print "Testing " + check + " :", try: evalResult = eval(check) gotException = False except: actualException = sys.exc_info()[1] gotException = True gotExpectedException = (str(actualException) == expectedException) if gotException and gotExpectedException: if msg: print " Passed!" return True elif not gotException: if msg: print " Failed! I expected an exception, but instead I got the result: " + \ str(evalResult) return False else: # must be true that (not gotExpectedException) if msg: print " Failed! I expected this Exception: " + \ expectedException + " but instead I got this exception: " + \ str(actualException) return False def sumList(myList): if (len(myList) == 0): return 0 else: first = myList[0] rest = myList[1:] return first + sumList(rest) new_check_expect("sumList([])",0) new_check_expect("sumList([2,3,4])",9) new_check_expect("sumList([2])",2) def largestOfList(myList): if (len(myList) == 0): raise Exception("can't find largest of an empty list") if (len(myList) == 1): return myList[0] else: first = myList[0] largestOfRest = largestOfList(myList[1:]) if ( first > largestOfRest): return first else: return largestOfRest check_exception("largestOfList([])","can't find largest of an empty list") new_check_expect("largestOfList([3])", 3) new_check_expect("largestOfList([5,7,1])", 7) new_check_expect("largestOfList([7,5,1])", 7) new_check_expect("largestOfList([1,5,7])", 7) # consume: a list of integers # produce: how many of those integers were divisible by 5 def countDivByFive(theList): if (len(theList)==0): return 0 if (len(theList)==1): if (theList[0]%5 == 0): return 1 else: return 0 else: if (theList[0]%5 == 0): return 1 + countDivByFive(theList[1:]) else: return 0 + countDivByFive(theList[1:]) new_check_expect("countDivByFive([])", 0) new_check_expect("countDivByFive([1])", 0) new_check_expect("countDivByFive([1,5,7])", 1) new_check_expect("countDivByFive([1,5,7,45])", 2) new_check_expect("countDivByFive([5,10,15,20])", 4) new_check_expect("countDivByFive([5,8,3,2])", 1) # consume: a list of integers # produce: a new list, with only the integers divisible by five def onlyDivByFive(theList): if (len(theList)==0): return [] if (len(theList)==1): if (theList[0]%5 == 0): return [ theList[0] ] else: return [] else: if (theList[0]%5 == 0): return [ theList[0] ] + onlyDivByFive(theList[1:]) else: return [] + onlyDivByFive(theList[1:]) new_check_expect("onlyDivByFive([])",[] ) new_check_expect("onlyDivByFive([1])", []) new_check_expect("onlyDivByFive([1,5,7])",[5] ) new_check_expect("onlyDivByFive([1,5,7,45])", [5,45]) new_check_expect("onlyDivByFive([5,10,15,20])",[5,10,15,20] ) new_check_expect("onlyDivByFive([5,8,3,2])", [5]) # consume: anything # produce: boolean, True if the thing is a string def isString(x): return type(x)==str new_check_expect("isString('foo')",True) new_check_expect("isString(12)",False) new_check_expect("isString(True)",False) new_check_expect("isString(['foo'])",False) # consume: a list # produce: how many of the things on the list are strings def countStrings(lst): if (len(lst)==0): return 0 if (len(lst)==1): if isString(lst[0]): return 1 else: return 0 else: if isString(lst[0]): return 1+ countStrings(lst[1:]) else: return countStrings(lst[1:]) new_check_expect("countStrings([])",0) new_check_expect("countStrings(['foo','bar',45,4.5])",2) new_check_expect("countStrings([45,4.5,True])",0) new_check_expect("countStrings([3,'foo','bar',45,4.5])",2) new_check_expect("countStrings([45,'bar',4.5,True])",1) # consume: a list of integers # produce: how many of those integers were divisible by 5 def countDivByFive(theList): if (len(theList)==0): return 0 if (len(theList)==1): if (theList[0]%5 == 0): return 1 else: return 0 else: if (theList[0]%5 == 0): return 1 + countDivByFive(theList[1:]) else: return 0 + countDivByFive(theList[1:]) new_check_expect("countDivByFive([])", 0) new_check_expect("countDivByFive([1])", 0) new_check_expect("countDivByFive([1,5,7])", 1) new_check_expect("countDivByFive([1,5,7,45])", 2) new_check_expect("countDivByFive([5,10,15,20])", 4) new_check_expect("countDivByFive([5,8,3,2])", 1)