Problem Set 3 FAQ

Problem Set 3 FAQ
- General questions
- Questions on problem 1 (Thinking recursively)

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

Do our functions for problems 3-4 have to be recursive?

Yes, unless the problem states otherwise.
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 ('').
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.
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
```
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)

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.