The TA will guide you through a brief problem-solving exercise that you will complete on paper. It is designed to help you see how well you’ve mastered the key concepts from Problem Sets 0 and 1.
Note that the exams will also be paper-only, so it’s important that you are able to solve problems without relying on Spyder, on online resources, or on too much help from other people.
If you haven’t already created a folder named cs111 for your
work in this course, follow these
instructions to do so.
Then create a subfolder called lab3 within your cs111 folder,
and put all of the files for this lab in that folder.
Access the template that we have created by clicking on this link and signing into your Google account as needed.
When asked, click on the Make a copy button, which will save a copy of the template file to your Google Drive.
Select File->Rename, and change the name of the file to
lab3.
Consider the following recursive function:
def mystery(a, b): """ mystery does something and then returns something. parameters: a -- an int b -- an int """ if a >= b: return b else: myst_rest = mystery(a * 2, b // 2) return a + myst_rest
Trace the execution of the call
mystery(1, 32)
by taking the following steps:
In lab3, find the template show below:
mystery(1, 32)
--------------
a = 1
b = 32
myst_rest = mystery(2, 16) = ...
return ...
mystery(2, 16)
--------------
a = 2
b = 16
myst_rest = ...
return ...
mystery( )
---------------------
a = ...
b = ...
myst_rest = ...
return ...
Complete this template so that it traces the series of recursive calls. In particular, you should:
Include a separate “frame” for each call. We have filled in some of the components of the frames for the first two calls for you, and we have given you a template for the third call. You should add frames for additional calls as needed, all the way down to the base case.
Begin each frame with a line that explicitly states the values assigned to the parameters, as we have done for the first two calls.
Next, if the call is a base case, you can simply show the
value that is returned (omitting the line for myst_rest). If
the call is a recursive case, you should show the recursive
call on the line for myst_rest (as we have done for the
first call).
Once you have reached the base case, you should work your way
back through the frames for the previous calls. Add in both
the results of the recursive call (i.e, the value assigned to
myst_rest) and the value returned by the call itself.
Debugging is an essential skill in computer programming. We’d like to emphasize some common debugging techniques and tips that will help you diagnose problems with your programs.
Begin by downloading the following file: lab3.py
Make sure to put the file in your lab3 folder. If your
browser doesn’t allow you to specify where the file should be
saved, try right-clicking on the link above and choosing
Save as... or Save link as..., which should produce a
dialog box that allows you to choose the correct folder for
the file.
Open the file in Spyder, and you should see the following
num_consonants() function.
def num_consonants(s): """ returns the number of consonants in s parameter: s is a string of lower-case letters """ if s == ' ': return 0 else: num_in_rest = num_consonants(s[1:]) if s[0] not in 'aeiou': return num_in_rest else: return num_in_rest + 1
Let’s see how to use our debugging techniques to debug the function, which has one or more bugs.
In this task, we will design and implement a function remove_spaces(s)
that takes string s and that uses recursion to construct and return
a string in which all of the spaces have been removed.
For example:
>>> remove_spaces('hi how are you?') result: 'hihowareyou?' >>> remove_spaces(' fine thanks! ') result: 'finethanks!'
Let’s start by determining the base case(s). When is the problem simple/small enough to be solved directly (without first solving a smaller subproblem)?
Next, we need to design the recursive case. In doing so, it helps to consider some concrete cases. For example:
remove_spaces('a b c d')
remove_spaces(' b c d')
Now that you have your design, here are the remaining steps:
Implement remove_spaces(s), adding it to your lab3.py
file.
Remember to add a docstring to the function that describes its behavior, its parameters, and its return value.
Once you think the function is ready, run your lab3.py
file and test the function from the console.
Debug the function as needed until it works correctly. Don’t forget that you need to re-run the file after making changes to the function.
If you need help with debugging, ask a staff member! You can also take advantage of the Debugging Tips page.
For extra practice on the basics of function calls, you should try tracing the following function on paper.
def mystery(a, b): """ takes two numbers, a and b, and does something with them! """ print(a, b) if a > b: c = a + 4 elif b > a: c = b - 2 else: c = -1 return c a = 3 b = 4 c = 5 b = mystery(c, a) print(a, b, c)
Create two tables – one for mystery and one for the variables in
the global scope – and fill in those tables to show how the values of
the variables change over time. In addition, you should answer the
following questions:
Based on your tracing, what do you predict will be the output of this program?
At the end of the program, the global variable c still
has a value of 5. Why does this make sense?
Complete any of the problems listed under the List-1 collection of problems on CodingBat. These problems provide good practice with writing functions with lists. Make sure to use recursion when solving them!
There is nothing to submit for today’s lab. Rather, there is an attendance sheet to sign, and staff members may check that you made a good effort on the assigned tasks during the lab. Don’t worry if you didn’t finish all of the tasks during lab.
If you didn’t finish, we encourage you to try to finish the lab on your own. You can check your work by consulting the solutions that will be posted on the Labs page on Wednesday.
Last updated on September 23, 2024.