Problem Set 9 - Due Tue, May 5, 2020 at 23:59pm
- New material: Slides and notebooks from Lec 20/21 Recursion, and Lab11: Recurison.
- Think Python, Ch. 5 Section 8: Recursion
About this Problem Set
The purpose of this problem set is to give you practice with:
- Recursion, and how it relates to iteration,
- In the context of printed output...
- and also in the context of
There are three tasks:
Task 0 is a survey. We'd like to hear from you about how the semester went, and in particular about the effectiveness of the various things we experimented with during our unprecedented remote learning period.
In Task 1 (Partner Task), you will write an recursive function to print an hourglass shape of alternating characters.
- In Task 2 (Partner Task), you will write a recursive function that draws a tree similar to the tree from problem set 3 task 2.
There is also an ungraded challenge task:
- Challenge 1 invites you to customize your tree function to create your own beautiful recursive pattern.
If you want to find a partner to work with (on any or all parts of the pset), you can use this Piazza post.
The CS111 Problem Set Guide gives an overview of psets, including some tips for working remotely with a partner.
Follow the style guidelines in the CS 111 Code Style Guide
- All code for this assignment is available in the
ps09folder in the
cs111/downloaddirectory within your
Task 0: CS 111 Survey
Please use this link to access the Spring 2020 CS 111 end-of-semester survey. We are trying to learn as much as possible about the effectiveness of our materials this semester, especially during remote learning, so we really appreciate any feedback that you have time to provide.
The task 1 rubric shows how this task will be graded, and can be used as a checklist to make sure you are done with the task (but remember that all we require now is an honest attempt).
Note: before starting this task, you should complete at least parts 0 and 1 of the lab on recursion.
For this task, you will create a new file named
define a function named
hourglass in that file. Your function
definition must have the following contract:
def hourglass(numSpaces, size, char1, char2):
Also, you will need to fill in the documentation string for this function describing what it does according to the instructions and examples below.
hourglass function should print an hourglass shape like those shown here:
******** ----- ====== %%% ||| **** $ - == %%% ||| **** ----- ====== ********
The parameters to
hourglass determine how many spaces the hourglass is
indented, how wide the longest row is, and the two characters that are
alternated to complete the shape.
hourglass function must be recursive, and it may not use any
loops. As a specific example, a call to
hourglass(4, 7, '*', '-') would
print the following output:
******* ----- *** - *** ----- *******
sizeparameter is 0 or negative, nothing is printed, and if the
sizeparameter is 1 or 2, only a single row is printed:
In : hourglass(3, 2, '#', ':') ## In :
numSpacesparameter controls indentation, so the spaces have to be added to every printed line:
In : hourglass(4, 3, '-', ':') --- : --- In : hourglass(8, 3, '-', ':') --- : --- In :
- Think carefully about the relationships between the parameters for different recursive calls. Make sure that you can see how a smaller recursive call fits into a larger one. If you need to, use the case-by-case approach described in the lecture material on recursion, particularly in the video for part 2 of the lecture.
The task 2 rubric shows how this task will be graded, and can be used as a checklist to make sure you are done with the task (but remember that all we require now is an honest attempt).
Note: before starting this task, you should complete part 2 of the lab on recursion.
For this task, you will create a recursive
tree function that draws a
branching pattern using
turtle graphics, quite similar to the tree
drawn in problem set 3 task 2. Here is an example of the
In the tree, everything starts with a trunk, and the first parameter of the
tree function specifies the length of the trunk. Unless it is just a
leaf, each tree has three branches: one to the left, one to the right,
and one in the middle. Of course, each of these branches is actually an
entire smaller tree, as shown in this image:
Note that the three trees in this image have been drawn starting from different positions and orientations just to show how they fit into each other. Here is another image that shows how different trunkLength parameters result in different trees if the other parameters are held constant:
tree.py file contains a blank definition of the
which is missing a docstring. You must fill in the docstring for the
tree function with your own description of how it works, and you
should do this before you begin to write your code.
tree function takes the following parameters:
trunkLength: This is the length of the line drawn to get to the base of the three branches. The left and right branches for a given tree have
trunkLengthvalues equal to 60% of the base value, while the middle branch has
trunkLengthequal to 75% of the base value.
leafLength: This sets a lower limit on the trunk length. If the
trunkLengthargument is less than this value, a leaf will be drawn instead of a branching tree.
branchAngle: This controls the angle between the middle branch and the two side branches. The branch angle for all three branches at each step is 80% of the base branch angle, so smaller sub-branches have more acute angles than the whole tree.
branchColor: This determines the color of each branch.
leafColor: This is used as the color for the leaves.
In addition to these parameters, the pen size for each branch is 1/10th
its length. For leaves, draw a straight line with length equal to the given
trunkLength and pen size set to 75% of that trunk length. Note that the
length of each leaf is not necessarily equal to
leaves are drawn when the
trunkLength parameter is less than or equal
Your job is to fill in the
tree function in
tree.py so that it draws the
exact shape shown above when called with the following arguments (which
are the defaults in the testing code):
tree(100, 20, 70, 'Sienna', 'SpringGreen')
Note that if you call that yourself without any setup, the image should look like this:
Note one more important fact: when the
tree function is finished, the
turtle cursor ends up back in the exact position it started from. This
is a critical factor in making the recursion work properly (
be recursive and may not use loops).
Feedback: Time Spent File
As in the previous psets, your time spent submission for this pset will
involve entering values for the variables in the
How to turn in this Problem Set
- Your task 0 submission is complete when you have submitted the survey form. Thank you for helping us improve CS 111 for future semesters!
- Each team member should save their
tree.pyfiles in their
- Save your filled-out
ps09folder as well.
- Note: It is critical that the name of the folder you submit is
ps09, and your submitted files are
myTree.png. In other words, do not rename the folder that you downloaded, do not create new files or folders (except
myTree.png), and do not delete or re-name any of the existing files in this folder.
- Drop your entire
ps09folder in your
dropfolder on the
csserver using Cyberduck by 11:59pm on Tuesday, May 5, 2020.
- Under current conditions, you are only required to submit an attempt.
- As always, you may take a 24-hour extension on this pset by filling out the late submission form.
tree function is working, copy your original code into a
second function called
fancyTree. For this challenge, modify that
function to draw whatever kind of tree you like. You may change the
number or meaning of the parameters, the constants in the code that
define the relationships between the different recursive function frames,
or whatever you wish. Some inspiration:
Along with the code in your
tree.py file, when your
function is done, take a screenshot of it and submit a file named
myTree.png showcasing what it looks like.