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.
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.
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 how to write one of the functions for this problem. Do you have any hints?
We encourage you to start with some concrete cases, as we’ve shown
you in lecture and in the description of the second function
from Problem 3 (combine
).
Although it isn’t strictly necessary, we also 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 the third suggestion in our answer for question 7 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 the third suggestion in our answer for question 7 in the section on General Questions above.
I’ve written an add
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!
I’m having trouble implementing contains(s, c)
.
Can you provided any more detail?
First, let’s remind ourselves of what the contains
function is
supposed to do:
contains(s, c)
should return True
if the single character c
is found somewhere in the string s
. For example, the call
contains('recurse', 'u')
should return True
, because 'u'
is contained in 'recurse'
.
contains(s, c)
should return False
if the single character
c
is not found in the string s
. For example, the call
contains('bye', 'x')
should return False
, because 'x'
is not contained in
'bye'
.
Also, we are not allowed to use the in
operator, since it would
eliminate the need to recursively process the string!
In the problem itself, we’ve given you some pseudocode that you should use as the basis of your solution. In particular, we’ve shown you the basic structure of the function – including the the two base cases.
The first base case occurs when the string that we’re reducing
(s
) is as small as possible – i.e., when s
is empty. In this
case, the character c
can’t possibly be contained in s
, and
thus we can return the appropriate boolean value for that
conclusion.
The second base case is when the first character in s
is the one
that we are looking for. If this is the case, we know that c
is contained in s
, and thus we can return the appropriate
boolean value for that conclusion.
To figure out what should happen after the recursive call, you should use concrete cases as we’ve shown in lecture. For example:
We know that contains('recurse', 'u')
should call
contains('ecurse', 'u')
.
What should each of these calls return, based on what this function is supposed to do?
How can we use the value returned by contains('ecurse', 'u')
to figure out what contains('recurse', 'u')
should return?
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 the third suggestion in our answer for question 7 in the section on General Questions above.
Last updated on February 5, 2024.