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 FAQs for PS 1-3, and the page we have assembled with info about common Python errors.
One of my functions that processes a string seems to have the correct logic, but it returns the wrong answer. Do you have any suggestions?
We’ve noticed many problems that stem from comparisons involving the wrong type of value. Python will not throw an error in these cases, which can make the problem especially difficult to diagnose.
In general, if you’re checking the elements of a string, you must
compare them to other string values as well. A common problem that
we’ve seen is that people will check to see if a character in the
string is either a 0 or a 1 with code that looks like this:
# this is incorrect! if b[0] == 0: # is the first character in b a zero? return ...
This is incorrect because we’re comparing a string with an
integer. The string '0' will never equal the integer 0, so the
boolean expression will never return True.
Instead, we need to compare the first character of b with a
string. The following code shows the correct way to check a
character in b.
# this is correct if b[0] == '0': # note the quotes around the 0 return ...
Make sure that all comparisons you make with strings are done with strings and not integers.
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 description of how to use this tool at the end of Problem Set 1, 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 the print statements before you submit
your work!
Trace through concrete cases. For example, let’s say that you’re
trying to determine the logic for the recursive case of
bin_to_dec. We have required that you process the input string from
right-to-left. That means that you should be making your recursive
call on a slice that includes everything but the last digit.
Consider the initial call bin_to_dec('1101'). It will
result in a series of calls:
bin_to_dec('1101') bin_to_dec('110') bin_to_dec('11') bin_to_dec('1') # 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:
bin_to_dec('1101') --> 13 bin_to_dec('110') --> 6 bin_to_dec('11') --> 3 bin_to_dec('1') --> 1
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 bin_to_dec('11') to
determine the solution to bin_to_dec('110')? How could you
use the solution to bin_to_dec('110') to determine the
solution to bin_to_dec('1101')?
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.
How do I get started on dec_to_bin?
Remember that dec_to_bin is a function that takes an integer n
and returns a string of ‘0’ and ‘1’ characters that represents n
in binary. This means you should build your result by concatenating
strings, not by adding integers together. Remember also that you
can’t add an integer to a string.
'0101' + 0 # wrong '0101' + '0' # correct
You should start with base case(s) that handle an n value of
either 0 or 1, because you already know the binary string that
each of those values maps to. Make sure that you return a string
in these cases and not an integer.
For the recursive case, review the lecture notes on binary numbers
to see the algorithm we can use to compute the binary string. This
can be done by computing only the right-most digit and then
delegating the rest of the work to recursion. What number can you
pass to the recursive call to dec_to_bin so that you get the
binary string representing the rest of n? You can determine this
number by reviewing the material in the lecture notes on binary
shifts and the decimal-to-binary algorithm.
How do I get started on bin_to_dec?
The lecture notes on binary numbers will help for bin_to_dec as
well. In this function, you will want to set up your base case(s)
to check for the strings '0' or '1', and then handle all other
numbers in your recursive case.
Remember that you are required to work on the binary string from the right to the left. This means that in your recursive case you need to determine the rightmost bit of the number and compute the decimal number belonging to the rest of the bits in the string. With these two numbers, you can make the decimal representation of the binary string you are given.
One of my functions for this problem seems to have the correct logic, but it returns the wrong answer. Do you have any suggestions?
Check to make sure that your boolean expressions are correct.
In particular, if you are using the and operator or the or
operator, make sure that both sides of the operator are true
boolean expressions – i.e., expressions that evaluate to
True or False.
For example, let’s say that we wanted to check if variables
x and y are both 10. The following does not work:
if x and y == 10: # wrong!
Although Python doesn’t complain about this code, the
expression after the if doesn’t actually check if both x and
y are 10, because the left-hand side of the and operator just
includes the variable x, which doesn’t compare x to anything.
Here’s a corrected version:
if x == 10 and y == 10: # correct!
Note that both sides of the and operator are now expressions that
evaluate to True or False, as they should be.
You may also want to review the answer to the first general question at the start of this FAQ.
How can we handle the case of add_bitwise in which we need to
carry a one?
In add_bitwise you add two binary strings together one digit at
a time. In the case that the rightmost bits of both strings are
‘1’ and ‘1’, you will need to carry a one to the next
column. Since we are implementing add_bitwise recursively, we
can only work on one column at a time.
To see how to add the one to the result, consider an example of using elementary-school arithmetic with binary numbers:
1011 + 0101 ------
When we add the two ones on the right together, we get 0, but we have to carry the 1 to the next column. If you did this by hand, you would probably write the following.
1
101 1
+ 010 1
-------
0
When doing things by hand, this is fine, but it doesn’t really work recursively.
Let’s rearrange the addition to something we could do in
our situation. That is, we first call add_bitwise to sum the
rest of the binary strings without the carry bit, and then we can
use a second call to add_bitwise to add in the carry bit.
101 1 + 010 1 ------- 111 0 + 1 ------- 1000 0
This adds the carry bit to the rest of the binary result, and so we can just concatenate our zero bit to that string, and we’re done!
We provided additional detail about this problem in lecture.
I’m still having trouble with add_bitwise().
Any other suggestions?
First, we strongly recommend that you make the initial recursive call–the one that adds everything but the rightmost bits–at the very start of your recursive case, and store its return value in a variable. It should look something like this:
def add_bitwise(b1, b2): """ your docstring goes here """ if ... # handle your base case(s) here else: sum_rest = add_bitwise(..., ...) # now decide what you will return
Note that we make the recursive call as the first statement in the
recursive case, and store its return value in the variable sum_rest.
You can then decide what you will return, building the return value
on the value of sum_rest.
As the problem set suggests, adding the carry bit should be done
using a second recursive call. In the example from the previous
question, we saw that we needed to add a carry bit of '1' to the
value '111'. How could you construct a recursive call to
add_bitwise() to add those two numbers? Now modify that specific
recursive call so that it works whenever you have a carry bit.
What should you replace the '111' with in the recursive call
to make it work for any situation involving a carry bit?
Last updated on April 28, 2025.