Problem Set 10 - Due Friday, May 3 at 23:59 EST

Reading

  1. Slides and notebooks from Lec 20 Introduction to Recursion, Lec 21 Introduction to Fruitful Recursion and Turtles, Lec 22 More Recursion and Lab 11 Nonfruitful and Fruitful Recursion.

  2. Think Python, Sec 5.8--5.10: Recursion

  3. Think Python, Ch. 6: Fruitful Functions (includes more on Recursion, plus other useful information)

About this Problem Set

The goal of this problem set is to give you practice with nonfruitful and fruitful recursion in the context of printing patterns with textual characters, drawing turtle pictures, and creating cs1graphics pictures.

There are four tasks in this problem set:

  1. In Task 1 (Individual Task), you will define a recursive function named hourglass that prints an hourglass shape of characters to the screen.

  2. In Task 2 (Individual Task), you will write a recursive function that draws a recursive L-shaped pattern using Turtle World.

  3. In Task 3 (Partner-recommended Task), you will define a fruitful recursive function that draws a shrub pattern using Turtle World and returns information about the pattern.

  4. In Task 4 (Partner-recommended Task), you will generate a recursive cs1graphics pattern and return information about the pattern.

Note that Tasks 3 and 4 are both partner-recommended tasks. You may choose to work with a partner on one or both tasks, but you may not work with two different partners on the different tasks. Use this shared Google Doc to find a partner for this pset.

Notes:


Task 1: Hourglasses

This is an individual problem which you must complete on your own, though you may ask for help from the CS111 staff.

In this task, open the provided file named hourglass.py and define in it a recursive function named hourglass that prints an hourglass shape of characters to the screen. You must use recursion (no loops are allowed).

The function is invoked as hourglass(indent, width, char1, char2).

  1. indent is the number of spaces printed on the left of each line
  2. width is the maximum number of characters printed per line at the topmost and bottommost lines of the hourglass.
  3. char1 and char2 are the two characters in the hourglass. The hourglass should consist of alternating lines of each character, beginning with char1.

The top line of the hourglass shape consists of width copies of char1 and begins with no spaces. Each subsequent line has two fewer characters and begins with one more space than the previous line, until a line with just one or two characters is reached. Then the lines start growing again in the opposite order.

If width is less than or equal to zero, nothing should be printed.

The following invocations of the hourglass function produce the output shown below.

In [2]: hourglass(0, 11, '&', '%')
&&&&&&&&&&&
 %%%%%%%%%
  &&&&&&&
   %%%%%
    &&&
     %
    &&&
   %%%%%
  &&&&&&&
 %%%%%%%%%
&&&&&&&&&&&

In [3]: hourglass(0, 12, 'x', 'o')
xxxxxxxxxxxx
 oooooooooo
  xxxxxxxx
   oooooo
    xxxx
     oo
    xxxx
   oooooo
  xxxxxxxx
 oooooooooo
xxxxxxxxxxxx

In [4]: hourglass(5, 7, '*', '-')
     *******
      -----
       ***
        -
       ***
      -----
     *******

In [5]: hourglass(0, 1, 'A', 'B')
A

In [6]: hourglass(0, 2, 'C', 'D')
CC

In [7]: hourglass(4, 1, 'E', 'F')
    E

In [8]: hourglass(7, 2, 'G', 'H')
       GG

In [9]: hourglass(9, 0, 'I', 'J') # Nothing printed for this case

In [10]: hourglass(3, -17, 'K', 'L') # Nothing printed for this case

Notes:


Task 2: Drawing Ls

This is an individual problem which you must complete on your own, though you may ask for help from the CS111 staff.

Inside the ps09 folder, open the file called drawLs.py. Within drawLs.py, you will define a new function, drawLs, so that it causes a turtle to draw a pattern of capital L letters. Your function should take two arguments:

  1. size indicates the length of the vertical edge of the L shape
  2. levels indicates the number of levels of recursion.

Each successive L is half the size of its predecessor. Below are example invocations of the drawLs function with different levels.

drawLs(200,0)
drawLs(200,1)
drawLs(200,2)
drawLs(200,3)
drawLs(200,4)
drawLs(200,5)

Details on how to draw a single L shape are shown below:

Notes:

    def run(levels):
      initializeTurtle()
      drawLs(200,levels)

 


Task 3: Turtle Shrubs

This task is a partner-recommended problem in which it is strongly recommended that you work with a partner as part of a two-person team. If you work with a partner on multiple tasks in this problem set, you must work with the same partner for all tasks. Use this shared Google Doc to find a partner for this pset.

In this task, you'll write a fruitful recursive function named shrub that draws a tree pattern with a turtle and returns a tuple of values (see below for details). Your shrub function should be invariant with respect to the turtle's position and direction. Define your function in the shrub.py file in the ps10 folder.

A turtle shrub is a variation of the turtle tree in Lec 22 More Recursion

It is created by the shrub function, which takes four parameters in order:

  1. trunkLength: the length of the branch at the base of the shrub.
  2. angle: the angle relative to the trunk for the right and left branches
  3. shrinkFactor: the trunk of the right branch is shrinkFactor times trunkLength, and the trunk of the left branch is shrinkFactor*shrinkFactor times trunkLength
  4. minLength: the minimum branch length in the shrub.

The shrub function returns a pair (a tuple with two elements) of:

  1. The total number of branches in the shrub, including the trunk
  2. The total length of branches in the shrub, including the trunk

 

Below are sample invocations of the shrub function, with the magenta text indicating the value returned by the invocation, i.e., the number of branches in the shrub:

shrub(100, 15, 0.8, 60) -> (4, 308.0)
shrub(100, 15, 0.8, 50) -> (7, 461.6)
shrub(100, 15, 0.8, 10) -> (232, 3973.9861913600025)
shrub(100, 30, 0.82, 10) -> (376, 6386.440567704483)
shrub(200, 90, 0.75, 10) -> (232, 5056.675148010254)

Notes:

 


Task 4: Recursive Squares

This task is a partner-recommended problem in which it is strongly recommended that you work with a partner as part of a two-person team. If you work with a partner on multiple tasks in this problem set, you must work with the same partner for all tasks. Use this shared Google Doc to find a partner for this pset.

In this task, you will use cs1graphics to draw multi-colored recursive squares patterns that look like this:

You should start this problem by reviewing the cs1graphics recursion examples from the end of the Notebook in Lec 20 Introduction to Recursion.

You will write all code for this task in the recursiveSquares.py file within the ps10 folder.

All subtasks of this task are checked by Codder but you should first run and test them in Canopy.

Subtask 4a: recursiveSquares

In this subtask, you will define a nonfruitful function recursiveSquares that draws the recursive squares pattern but does not return any result. The recursiveSquares function has the following function header:

def recursiveSquares(canvas, patternSide, upperLeftX, upperLeftY,
                     minSide, color1, color2, color3):

Here is the meaning of the parameters, which are further illustrated in the eight examples in the table following the bullet points.

recursiveSquares(canv,512,0,0,600,
'red','blue','cyan')
recursiveSquares(canv,512,0,0,512,
'red','blue','cyan')
recursiveSquares(canv,512,0,0,256,
'red','blue','cyan')
recursiveSquares(canv,512,0,0,128,
'red','blue','cyan')
recursiveSquares(canv,512,0,0,64,
'red','blue','cyan')
recursiveSquares(canv,512,0,0,32,
'red','blue','cyan')
recursiveSquares(canv,512,0,0,16,
'red','blue','cyan')
recursiveSquares(canv,512,0,0,8,
'red','blue','cyan')

Notes:

Subtask 4b: recursiveSquaresCount

In this subtask you will define a fruitful function named recursiveSquaresCount that takes the same arguments and draws the same pattern as recursiveSquares from Subtask 4a but also returns the total number of squares drawn in the pattern. For example, in the following table, the number after the => in each invocation of recursiveSquaresCount shows the integer that should be returned.

recursiveSquaresCount(canv,512,0,0,600,
'red','blue','cyan') => 0
recursiveSquaresCount(canv,512,0,0,512,
'red','blue','cyan') => 1
recursiveSquaresCount(canv,512,0,0,256,
'red','blue','cyan') => 4
recursiveSquaresCount(canv,512,0,0,128,
'red','blue','cyan') => 13
recursiveSquaresCount(canv,512,0,0,64,
'red','blue','cyan') => 40
recursiveSquaresCount(canv,512,0,0,32,
'red','blue','cyan') => 121
recursiveSquaresCount(canv,512,0,0,16,
'red','blue','cyan') => 364
recursiveSquaresCount(canv,512,0,0,8,
'red','blue','cyan') => 1093

Notes:

Subtask 4c: recursiveSquaresCountColors

In this subtask you will define a fruitful function named recursiveSquaresCountColors that takes the same arguments and draws the same pattern as recursiveSquares from Subtask 4a but also returns a triple (i.e., a 3-element tuple) with these three components:

  1. The number of squares in the pattern drawn with color1;

  2. The number of squares in the pattern drawn with color2;

  3. The number of squares in the pattern drawn with color3.

For example, in the following table, the number after the => in each invocation of recursiveSquaresCount shows the triple of integers that should be returned.

recursiveSquaresCountColors(canv,512,0,0,600,
'red','blue','cyan') => (0, 0, 0)
recursiveSquaresCountColors(canv,512,0,0,512,
'red','blue','cyan') => (1, 0, 0)
recursiveSquaresCountColors(canv,512,0,0,256,
'red','blue','cyan') => (1, 1, 2)
recursiveSquaresCountColors(canv,512,0,0,128,
'red','blue','cyan') => (6, 4, 3)
recursiveSquaresCountColors(canv,512,0,0,64,
'red','blue','cyan') => (11, 13, 16)
recursiveSquaresCountColors(canv,512,0,0,32,
'red','blue','cyan') => (46, 40, 35)
recursiveSquaresCountColors(canv,512,0,0,16,
'red','blue','cyan') => (111, 121, 132)
recursiveSquaresCountColors(canv,512,0,0,8,
'red','blue','cyan') => (386, 364, 343)

Notes:


Task 5: Honor Code Form and Final Checks

As in the previous psets, your honor code submission for this pset will involve defining entering values for the variables in the honorcode.py file.

If you wrote any function invocations or print statements in your Python files to test your code, please remove them, comment them out before you submit, or wrap them in a if __name__=='__main__' block at the end of a .py file. Points will be deducted for isolated function invocations or superfluous print statements.

It's a good idea to run Codder one last time before submission.


How to turn in this Problem Set