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.
Do our functions for problems 4, 5 and 6 have to be recursive?
Yes, unless the description of the function states otherwise. You should not be using list comprehensions or other constructs that you may already know about but that we haven’t covered in lecture.
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 ('').
I get an error message that mentions a TypeError when I add
something to a list. What should I do?
If you get something like the following error.
TypeError: can only concatenate list (not "int") to list
you are likely trying to add an integer to a list.
Suppose you have two lists called x and y.
x = [0, 1, 2] y = [3, 4, 5]
And you would like to make a list that contains [0, 1, 2, 3].
You might try doing the following:
x + y[0]
Unfortunately, this is not allowed in Python, because addition
between a list and an integer is not defined. If you think about
it, this makes sense: how would you add a list to an integer?
Instead, recall that the + operator can be used to concatenate
two lists. Knowing this, we can put y[0] inside its own list
and concatenate that with the list x.
x + [y[0]]
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 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.
What can I do if I’m encountering infinite recursion – i.e., an error with a message that says something like
RecursionError: maximum recursion depth exceeded
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
here.
When I test one of my functions, I’m getting an error message that looks something like this:
It seems the debugger cannot resolve ... This may make the debugger miss breakpoints in the standard library.
What does this mean?
This most likely means that your test call is producing infinite recursion. See the previous question for more info.
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 2.
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! See the next question for more details.
How can I use concrete cases to help me in designing or debugging one of my recursive methods?
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.
For 2-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.
I’m having trouble figuring out why my combine function
isn’t working. Do you have any hints?
As mentioned in the problem itself, the funtion needs to extract two different substrings that are then combined.
Although it isn’t strictly necessary, we encourage you to use separate variables for each substring that the function creates, and then you can use those variables in the return statement to construct the final return value.
Using variables in this way allows you to focus on one piece of the problem at a time, and it also allows you to use temporary print statements as needed to see what you are getting for each substring. This can be useful if your function isn’t working correctly, because it can allow you to see more clearly where the problem is occurring.
I’m having trouble coming up with the logic for one of the recursive functions. Do you have any suggestions?
See question 8 in the section on General Questions above.
I’m having trouble coming up with the logic for one of the recursive functions. Do you have any suggestions?
See question 8 in the section on General Questions above.
I’ve written a mul_pairs function that seems to have the correct
logic, but it doesn’t catch the base case on at least some of my test
cases. Instead, I end up with an IndexError. Any suggestions?
Check any if statement in your function that uses the or
operator or the and operator. Make sure that both sides of the
operator are boolean expressions that could produce True or
False on their own.
For example, let’s say that we want to test whether either the
variable x or the variable y is 0. The following
if statement does not work:
if x or y == 0: # wrong!
Instead, we would need to rewrite it as follows:
if x == 0 or y == 0: # correct!
Is our scrabble_score function required to call our
letter_score function? I’m confused about how to do so.
Yes, this is required!
Your letter_score function takes a letter as input and returns
the value of that letter as a scrabble tile. So if your
scrabble_score function needs the value of the first letter of
the string s, you can simply pass that letter into
letter_score:
letter_score(s[0])
You can either:
Make this call as part of an assignment statement in which you assign the return value to a variable, and then use that variable later on in your function.
Make this call as part of a larger expression – e.g., the
expression that you are using in your return statement.
I’m having trouble coming up with the logic for one of the recursive functions. Do you have any suggestions?
See question 8 in the section on General Questions above.
Last updated on September 23, 2024.