Problem Set 2 FAQ

General questions
Questions on problem 2 (More practice with writing functions)
Questions on problem 3 (Thinking recursively)
Questions on problem 4 (Fun with recursion, part I)
Questions on problem 5 (Tracing functions and list comprehensions)
Questions on problem 6 (Writing list comprehensions)
Questions on problem 7 (Fun with recursion, part II)

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 questions from the PS 1 FAQ, and the page we have assembled with info about common Python errors.

General questions

Do our functions for problems 4 and 7 have to be recursive?

Yes, unless the description of the function states otherwise. You should not be using list comprehensions or other constructs that may already know about on problems 4 and 7.
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 that 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 calledNone. 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.
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 use recursion to find the length of a string, and I attempt to do so using the following function:
```
def mylen(s):
    len_rest = mylen(s[1:])
    if s == '' or s == []:
        return 0
    else:
        return 1 + len_rest
```
This function will produce infinite recursion, because no matter what the value of s is, we begin by making a recursive call to mylen and assigning its return value to len_rest. In order to fix this, we need to move the recursive call after the base case. See the corrected function below.
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 to step through your function as it executes on one or more test cases. See our reminders for how to use this tool at the end of Problem 3.
- 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!
- Try tracing through concrete cases.
  
  For example, let’s say that you were trying to determine the logic for the recursive case of the num_vowels function from lecture. (This means that you would have already decided on the base cases and included code that handles them.)
  
  The first step in addressing the recursive case is deciding how to reduce the problem to a smaller subproblem. In this case, we can reduce the problem by “chopping off” the first character in the string, which means that we will make the recursive call on a slice that includes everything but the first character.
  
  Once we’ve decided how to reduce the problem, we’re ready to consider concrete cases. For example, consider the initial call num_vowels('code'). It will result in a series of calls:
```
num_vowels('code')
num_vowels('ode')
num_vowels('de')
num_vowels('e')
num_vowels('')      # base case
```
  And because each of these calls must return the correct value for its input, you can write down the correct return value for each call:
```
num_vowels('code') --> 2 
num_vowels('ode')  --> 2 (because there are 2 vowels in 'ode') 
num_vowels('de')   --> 1 (because there is 1 vowel in 'de')
num_vowels('e')    --> 1
num_vowels('')     --> 0
```
  Given these return values, ask yourself what you need to do with the value that is returned by the recursive call. How can you use the solution to the smaller subproblem to to determine the solution to the original problem? For the example above, how could you use the solution to num_vowels('de') to determine the solution to num_vowels('ode')? How could you use the solution to num_vowels('ode') to determine the solution to num_vowels('code')?
  
  In this case, we notice that sometimes we need to add 1 to the value returned by the recursive call, and sometimes we don’t. This means that we need to use an if-else statement to decide what to return, and we can use the trace of the concrete case to determine what test should be used for the if condition.
  
  A similar procedure can be followed for any recursive function. Once you have determined the base cases and the way in which you plan to reduce the original problem to one or more subproblems, write down the series of calls that will result from concrete cases, and ask yourself the types of questions that we mentioned above.

Questions on problem 2 (More practice with writing functions)

How do I start implementing is_mirror?

One hint is to begin by computing len(s)//2. What does this value represent? How can you use this value in conjunction with slicing to extract one or more components of the string s that could be useful in the context of this function?

You might also want to consider having your is_mirror function call your previous mirror function to do some of the work. Doing so isn’t required, but if you don’t call mirror, you will need to replicate at least part of what that other function does in order to determine if s is a “mirrored” string.

Questions on problem 3 (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, when we traced through the example mylen('wow'), 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 4 (Fun with recursion, part I)

I’m having trouble coming up with the logic for one of the recursive functions. Do you have any suggestions?

See the third suggestion in our answer for question 5 in the section on General Questions above.
When I make the recursive call in my sum function, the word sum is colored purple. Does that mean that I am calling the built-in sum function? If so, how do I make it call my sum function instead?

It may seem like your code is calling the pre-programmed sum function (because it is showing up in purple), but it actually isn’t. Once you define your own sum function, you are temporarily replacing the built-in sum function in the context of that Python file. Thus, when you call sum, you are calling your own sum function.

Questions on problem 5 (Tracing functions and list comprehensions)

In part 2, how much detail should we show in our trace of the list comprehension itself?

See the sample trace that we’ve included at the end of the problem for an illustration of the format that you should use.

Questions on problem 6 (Writing list comprehensions)

I’m having trouble using range. How do I create a list of numbers with it?

Recall that range(n) gives you a sequence of numbers from 0 to n-1. You can change the starting number by giving another parameter before n. For example, in order to get all the numbers from 2 to n-1, you could use range(2, n). It’s important that you do not put brackets around the call to range. Instead, you can use a call to range in conjunction with a list comprehension as in the following example:
```
[x*2 for x in range(5)]
```
If the length of the necessary list depends on the value of a variable, you can use the variable as the input to range. For example, let’s say that we want to write a function double(num_vals) that produces a list in which the integers from 0 to num_vals-1 are doubled. You could do something like this:
```
def double(num_vals):
    """ docstring goes here
    """
    return [2*x for x in range(num_vals)]
```
Note that we use the parameter num_vals as the input to range.
Do you have any hints for how I can use a list comprehension for problem 6 part 3?

Let’s say that we wanted to write a function that takes a list of numbers and returns a list containing only the odd numbers. We could do so using a list comprehension as follows:
```
def odd_vals(values):
    """ docstring goes here
    """
    return [x for x in values if x % 2 == 1]
```
Note that we’re using the parameter values as the list on which the list comprehension operates. The runner variable x takes on one value at a time from that list, and the unchanged value of x is included in the result—but only if the conditionx % 2 == 1 is True (i.e., if x is odd). In other words, the list comprehension is filtering the original list of numbers—keeping those that are odd and discarding the rest.

In problem 6 part 3, you will also need to use a list comprehension for filtering, but you will filter a list of strings based on whether the length of the string is shorter than the specified integer n.

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

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

Here again, it can help 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.