CS 111
Summer 2 2018

Problem Set 3 FAQ

Problem Set 3 FAQ

If you don’t see your question here, post it on Piazza or come to office hours! See the links in the navigation bar for both of those options.

You may also find it helpful to consult the general questions from the PS 2 FAQ, and the page we have assembled with info about common Python errors.

General questions

  1. Do our functions for problems 6 have to be recursive?

    Yes, unless the problem states otherwise. You should not be using list comprehensions on problems 6.

  2. Why do I keep getting an index error?

    If you get an error that looks something like the following:

    IndexError: string index out of range
    

    or

    IndexError: list index out of range
    

    it means that you are trying to access an element of a sequence (a string or list) using an invalid index.

    One common cause of this error stems from situations in which you have an empty string or empty list, and you try to access one of its elements using an expression like s[0]. Because there are no elements in an empty string or empty list, you end up with an IndexError.

    If you are encountering this error in a recursive function, you are likely not implementing your base case correctly. Make sure that you are correctly handling the case in which you have an empty string or empty list. Also, when checking for the empty string, make sure that you don’t put a space between the quotes. The empty string is represented by two quotes with nothing in between them ('').

  3. When I test one of my functions I’m getting an error message that ends with a line that says something like

    TypeError: Cannot convert NoneType object to...
    

    What am I doing wrong?

    This error probably means one of two things:

    • Your function is failing to return a value in certain cases. When a function doesn’t explicitly return a value, it implicitly returns a special value called None. Then, if the recursive case of your function is trying to operate on that return value (e.g., by adding something to it), you will get a TypeError like the one shown above, because you can’t add None to another value. Make sure that your function returns an appropriate value in all cases, and this error should go away.

    • Your function is explicitly returning None (for the index function in problem 5), and you are trying to operate on that value (e.g., by adding something to it). To prevent this from happening, you need to check for the case when the recursive call is returning None, and handle it appropriately.

  4. What can I do if I’m encountering infinite recursion?

    First, make sure you have implemented a base case in your function and that it works properly. Next, be sure that you are not calling the function recursively before the recursive case. As an example, let’s say I want to sum all the numbers from 1 to n, and that I attempt to do so using the following function:

    def sum(n):
        rest = sum(n-1)
        if n == 0:
            return 0
        else:
            return n + rest
    

    This function will produce infinite recursion, because no matter what the value of n is, we begin by making a recursive call to sum and assigning its return value to rest. In order to fix this, we need to move the assignment to the variable rest after the base case.

    def sum(n):
        if n == 0:
            return 0
        else:
            rest = sum(n-1)
            return n + rest
    
  5. How can I figure out where the problem is in one of my recursive methods?

    Here are three things that can help:

    • Use the [Python Tutor visualizer][tutor] to step through your function as it executes on one or more test cases. See our description of how to use this tool at the beginning of [problem 4][ps1pr4].

    • Add temporary print statements to your function. It helps if you can put a print statement at the very beginning of the function to print the values of the inputs, and then another print statement before each return statement to print the value being returned. For example, here is a version of the mylen function from lecture that does this:

      def mylen(s):
          """ returns the length of the sequence s
              input: s is a sequence (a string or list)
          """
          print('starting the call mylen(' + s + ')')    # add one print at the start
          if s == '' or s == []:
              print('mylen(' + s + ') is returning 0')   # print before returning
              return 0
          else:
              len_rest = mylen(s[1:])
              print('mylen(' + s + ') is returning', 1 + len_rest)   # here, too!
              return 1 + len_rest
      

      Make sure to remove those print statements before you submit your work!

    • Trace through concrete cases, and ask yourself the types of questions that are mentioned in our answer to the first question on the index() function below.

Questions on problem 1 (Thinking recursively)

  1. For part 3, I’m not sure how to count the number of stack frames. How do we know how many frames there will be, and how do we incorporate the global scope?

    When counting stack frames for a recursive function, there will be one stack frame for each call of the function, plus one extra stack frame for the global scope (the portion of the program that is outside of any function, and from which we are assuming the initial function call is made).

    For example, in lecture we traced through the example mylen('wow'), and we saw that we got four function calls: mylen('wow'), mylen('ow'), mylen('w'), and mylen(''). As a result, there would be five stack frames when we reach the base case: four from the calls to mylen, and one for the global scope.

Questions on problem 3 (Fun with recursion, part II)

  1. My index function works in some cases, but not in others. Do you have any suggestions?

    One thing that can help is to consider some concrete cases. For example, let’s assume that you’re following the suggestion mentioned in the assignment and using the mylen example from lecture as a model for this problem. That would mean that you are making recursive calls on a slice that includes everything but the first element.

    Consider the initial call index(5, [2, 3, 4, 5, 6, 7]). It will involve a series of calls:

    index(5, [2, 3, 4, 5, 6, 7])
    index(5, [3, 4, 5, 6, 7])
    index(5, [4, 5, 6, 7])
    etc.
    

    Given those calls, ask yourself two questions:

    • How far do the recursive calls need to go? Do they need to go all the way to the empty list (like they do in mylen), or is it possible to stop earlier? If it is possible to stop early in some cases, make sure to include the base case(s) that will do so. If not, make sure to have a base case for the empty list. Remember that you are not allowed to use the in operator in this function.

    • What do I need to do with the value that is returned by the recursive call? Remember that the recursive call is solving a smaller subproblem. How can you use the solution to that smaller subproblem to determine the solution to the original problem? For the example above, how could you use the solution to the subproblem index(5, [3, 4, 5, 6, 7]) to determine the solution to index(5, [2, 3, 4, 5, 6, 7])?

    Next consider the initial call index(8, [2, 3, 4, 5, 6, 7])– which is a call in which the value does not appear in the list at all. It will involve a series of calls:

    index(8, [2, 3, 4, 5, 6, 7])
    index(8, [3, 4, 5, 6, 7])
    index(8, [4, 5, 6, 7])
    etc.
    

    Given those calls, ask yourself two questions:

    • How far do the recursive calls need to go? Do they need to go all the way to the empty list (like they do in mylen), or is it possible to stop earlier? If it is possible to stop early in some cases, make sure to include the base case(s) that will do so. If not, make sure to have a base case for the empty list. Remember that you are not allowed to use the in operator in this function.

    • What do I need to do with the value that is returned by the recursive call? Remember that the recursive call is solving a smaller subproblem. How can you use the solution to that smaller subproblem to determine the solution to the original problem? For the example above, how could you use the solution to the subproblem index(8, [3, 4, 5, 6, 7]) to determine the solution to index(8, [2, 3, 4, 5, 6, 7])?

    Finally, keep in mind the following hint from the problem: In the recursive case, the decision about what to return will need to take into account the result of the recursive call. As a result, it is especially important that you store in a variable the value that is returned by the recursive call. This means that you need an if statement in the recursive case, and it needs to have a condition that is based on the result of the recursive call. In other words, you need to look at the value that is returned by the recursive call in order to decide what you should return.

  2. When I test my index function, I get a TypeError. Do you have any suggestions?

    See question 3 in the section on General Questions above.