CS8, 10F, H15, due Tue Lecture 11.30—Basics of Recursive Functions on Lists—Total points: ?

Available online as http://www.cs.ucsb.edu/~pconrad/cs8/10F/homework/H15—printable PDF

Name: (4 pts)   Umail Address: (4 pts)   @umail.ucsb.edu
Lab Section (2 pts)—circle one:  9am   10am   11am   noon   unknown   crashing 
You may collaborate with at most ONE other person on this homework assignment. If you do, please enter his/her name here:  
  (He/she should also enter your name on her/his assignment.)

This assignment is due in Lecture on Tuesday, 11.30.
It may ONLY be submitted in Lecture, at 2pm on Tuesday.

You must come IN PERSON to turn it in during your assigned Lecture section.

The reading for this assignment is the handout that was given out with this assignment—that handout is also available online in both HTML and PDF formats at http://www.cs.ucsb.edu/~pconrad/cs8/10F/homework/H15/handout

  1. (5 pts) Multiple choice: When testing whether the ith item of thisList is not equal to int, which of these is correct:

    1. if type(thisList[i]!=int):
    2. if type(thisList[i])!=int:
    3. if type(thisList)[i]!=int:
    4. if (type(thisList(i))!=int:

      Note: Your instructor included this problem on the homework because he kept typing the wrong choice—over and over again—while making up this week's lecture notes and homework problems, even though he knows full well which one is correct. Fortunately, the test cases caught the mistake before he put incorrect code in the lecture notes. As a result he (i) believes even more strongly in the power of test-driven development (ii) figures if he made the mistake, you might make it occasionally too, so it is worth reviewing which one is the right answer.

  2. (5 pts) Fill in the blanks with two words:

    In order to avoid an infinite loop, a correctly written recursive function has at least one _______ ________
    that does not use recursion.

  3. (5 pts) Fill in the blank with a short phrase:

    You can tell if a function is recursive by looking at its definition.
    It is recursive if the function definition contains ________________________________________

Please turn over for more...

...continued from other side

  1. (15 pts) Here is the largestInt function from the starting point file for lab06, rewritten as a recursive function.
    Two lines of code were left out. Please fill in the blanks.

    If you want to try your version, visit http://www.cs.ucsb.edu/~pconrad/cs8/10F/homework/H15/code where
    you can find a copy of the file largestIntRecursive.py with the blanks ready to fill in.

    def largestInt(listOfInts):
        return largest element of a list of ints
        By "largest", we mean a value that is no smaller than any other value in the list
          (There may be more than one instance of that value--e.g. in [7,3,7], 7 is largest
        listOfInts is a list of integers
        returns: False if the parameter is not not a list, contains something not an int,
           or is an empty list----otherwise, returns the largest value in the list
        if type(listOfInts)!=list or listOfInts==[]:
            return False
        # See if the first item on the list is something other than an int
        if type(listOfInts[0]) != int:
            return False
        maxSoFar = listOfInts[0]   
        if (len(listOfInts)==1):
            return maxSoFar
        # Compute the maximum in positions 1 through the end of the list
        # with a recursive call to largestInt
        maxOfRest = ____________________
        if (maxOfRest > maxSoFar):
            return _________        # what should be returned in this case?
            return _________         # what should be returned in this case?      
  2. (10 pts) In the function above, we find this segment of code:

    if type(listOfInts[0]) != int:
      return False

    Explain how, even though the function is only checking whether type(listOfInts[0])!=int—that is, it is only checking the value in position 0—function can still detect the presence of a non-int value at list position 3, as when the value of the listOfInts parameter is [17,92,42,"oops",18]

End of H15