Problem Set 9 - Due Tue, May 5, 2020 at 23:59pm


  1. New material: Slides and notebooks from Lec 20/21 Recursion, and Lab11: Recurison.
  2. Think Python, Ch. 5 Section 8: Recursion

About this Problem Set

The purpose of this problem set is to give you practice with:

There are three tasks:

There is also an ungraded challenge task:

If you want to find a partner to work with (on any or all parts of the pset), you can use this Piazza post.


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.

Task 1: hourglass

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 and 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.

Your 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.

Your 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:



Task 2: tree

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 output:

A branching tree with a brown trunk and branches and green leaves. The overall shape is similar to that of a maple leaf, with three prominent segments of leaves.

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:

Three trees of different sizes with indicators showing how the larger trees contain individual branches that are exactly the same as the entire smaller trees.

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:

Six trees of different trunk lengths (labeled 12, 16, 20, 24, 28, and 32). The first is just a thick green line with rounded ends, the next has a brown stem plus three green lines branching out from the tip, the second has two stems with five leaves (two branching from the middle; three from the tip, etc.).

The file contains a blank definition of the tree function, 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.

The tree function takes the following parameters:

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 leafLength, because leaves are drawn when the trunkLength parameter is less than or equal to the leafLength parameter.

Your job is to fill in the tree function in 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:

A tree pointing to the right instead of upwards and partially cut off by the edge of the window.

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 (tree must 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 file.

How to turn in this Problem Set

Electronic submission

Challenge 1: fancyTree

Once your 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:

A fern that branches differently to the right and to the left. A metalic 'shrub' with branches at 60° angles and a silvery color. A fancy tree with slightly randomized branch angles, trunk lengths, and also with random fruit.

Along with the code in your file, when your fancyTree function is done, take a screenshot of it and submit a file named myTree.png showcasing what it looks like.