# Examples of Recursive functions # P. Conrad for CS5nm, 12/02/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 # consumes: a list of integers # produces: an integer, how many odd numbers are in the list passed in def countOdd(myList): if (len(myList)==0): return 0 else: if myList[0]%2==1: return 1 + countOdd(myList[1:]) else: return countOdd(myList[1:]) new_check_expect("countOdd([])",0) new_check_expect("countOdd([-1,-2,-3])",2) new_check_expect("countOdd([2,4,6])",0) new_check_expect("countOdd([1,2,3,4,5])",3) # consumes: a list of integers # produces: integer, sum of all the negative numbers in the list passed in def sumNeg(lst): if (len(lst)==0): return 0 else: if lst[0] <= 0: return lst[0] + sumNeg(lst[1:]) else: return sumNeg(lst[1:]) new_check_expect("sumNeg([])",0) new_check_expect("sumNeg([-1,-2,-3])",-6) new_check_expect("sumNeg([2,4,6])",0) new_check_expect("sumNeg([-1,2,-3,4,-5])",-9) # consumes: a list of integers # produces: an integer, the smallest number on the list # exception: if lst is empty, raise Exception("can't find smallest of empty list") def smallest(lst): if len(lst)==0: raise Exception("can't find smallest of empty list") elif len(lst)==1: return lst[0] else: first = lst[0] smallestOfRest = smallest(lst[1:]) if ( first < smallestOfRest): return first else: return smallestOfRest new_check_expect("smallest([-1,-2,-3])",-3) new_check_expect("smallest([2,4,6])",2) new_check_expect("smallest([-1,2,-3,4,-5])",-5) new_check_expect("smallest([3,5,6,2,8])",2) check_exception("smallest([])", "can't find smallest of empty list") # consumes: a list of integers # produces: an integer, how many even numbers are in the list passed in def countEven(myList): if len(myList)==0: return 0 elif len(myList)==1: if myList[0]%2==0: return 1 else: return 0 else: if myList[0]%2==0: return 1 + countEven(myList[1:]) else: return 0 + countEven(myList[1:]) new_check_expect("countEven([])",0) new_check_expect("countEven([-1,-2,-3])",1) new_check_expect("countEven([2,4,6])",3) new_check_expect("countEven([1,2,3,4,5])",2) new_check_expect("countEven([5])",0) new_check_expect("countEven([6])",1) # consumes: a list of strings # produces: a list of integers, each one corresponding to the length of the corresponding string in the list passed in # Example: lengths(["This", "is", "a", "test"]) produces [4,2,1,4] # empty list produces empty list def lengths(myList): if len(myList)==0: return [] elif len(myList)==1: return [len(myList[0])] else: return [len(myList[0])] + lengths(myList[1:]) new_check_expect("lengths([])",[]) new_check_expect("lengths(['UCSB'])",[4]) new_check_expect("lengths(['CS5NM'])",[5]) new_check_expect("lengths(['Go','Gauchos'])",[2,7]) new_check_expect("lengths(['University','of','California','Santa','Barbara'])",[10,2,10,5,7]) # consumes: a list of strings # produces: a list of strings, only containing strings of length >= 5 # empty list produces empty list def bigWords(myList): if len(myList)==0: return [] else: if len(myList[0])>=5: return [ myList[0] ] + bigWords(myList[1:]) # keep the big word! else: return bigWords(myList[1:]) # drop the small word! new_check_expect("bigWords([])",[]) new_check_expect("bigWords(['UCSB'])",[]) new_check_expect("bigWords(['CS5NM'])",["CS5NM"]) new_check_expect("bigWords(['Go','Gauchos'])",["Gauchos"]) new_check_expect("bigWords(['University','of','California','Santa','Barbara'])", ["University","California","Santa","Barbara"]) # consumes: a list of strings # produces: a list of strings, only words that start with S or s # empty list produces empty list def sWords(myList): if ( len(myList)==0): return myList elif (myList[0][0]=='s' or myList[0][0]=='S'): return [ myList[0] ] + sWords(myList[1:]) else: return sWords(myList[1:]) new_check_expect("sWords([])",[]) new_check_expect("sWords(['UCSB'])",[]) new_check_expect("sWords(['CS5NM'])",[]) new_check_expect("sWords(['Go','Gauchos'])",[]) new_check_expect("sWords(['University','of','California','Santa','Barbara'])", ["Santa"]) new_check_expect("sWords(['Sally','sells','seashells','by','the'])", ["Sally",'sells','seashells'])