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

## Reading

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:

• Recursion, and how it relates to iteration,
• In the context of printed output...
• and also in the context of `turtle` graphics.

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.

Notes:

• 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

• When you're done with the task, fill out your time spent form and follow the submission instructions to submit your pset.

• All code for this assignment is available in the `ps09` folder in the `cs111/download` directory within your `cs` server account.

## 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 `hourglass.py` 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:

``````    *******
-----
***
-
***
-----
*******``````

Notes:

• If the `size` parameter is 0 or negative, nothing is printed, and if the `size` parameter is 1 or 2, only a single row is printed:

``````In [1]: hourglass(3, 2, '#', ':')
##

In [2]:``````
• The `numSpaces` parameter controls indentation, so the spaces have to be added to every printed line:

``````In [1]: hourglass(4, 3, '-', ':')
---
:
---

In [2]: hourglass(8, 3, '-', ':')
---
:
---

In [3]:``````
• 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.

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

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:

The `tree.py` 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:

• `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 `trunkLength` values equal to 60% of the base value, while the middle branch has `trunkLength` equal to 75% of the base value.
• `leafLength`: This sets a lower limit on the trunk length. If the `trunkLength` argument 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 `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 `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 (`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 `timeSpent.py` file.

## How to turn in this Problem Set

### Electronic submission

• 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 `hourglass.py` and `tree.py` files in their `ps09` folder.
• Save your filled-out `timeSpent.py` file in `ps09` folder as well.
• Note: It is critical that the name of the folder you submit is `ps09`, and your submitted files are `hourglass.py`, `tree.py`, and `timeSpent.py` (optionally also `myTree.png`. In other words, do not rename the folder that you downloaded, do not create new files or folders (except `hourglass.py` and possibly `myTree.png`), and do not delete or re-name any of the existing files in this folder.
• Drop your entire `ps09` folder in your `drop` folder on the `cs` server 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.

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

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