@extends('template')
@section('title')
Lab 11, Part 4: Fruitful recursion w/ Turtle graphics
@stop
@section('content')
# Lab 11, Part 4: Fruitful recursion w/ Turtle graphics
## Task 1. row
In last week's lab, we designed recursive Turtle functions that would draw a pattern a given number of times.
For example, when we invoked `row(3, 50)` it would draw **3** squares.
To make things more challenging, let's pretend the Turtle has a limited supply of ink. Instead of designing our function so that it repeats the design *X* number of times, let's limit it by how much “ink” is left.
Each pixel travelled represents a “drop of ink”. E.g. if the turtle moves `fd(30)` that's 30 hypothetical drops of ink. Thus, to complete a square, it would require 120 drops of ink (30 * 4).
In addition to limiting the distance travelled, we also want to find out **how many squares were drawn** with the given limit. I.e. we want to make the row function fruitful.
The following is the solution to this function. **Do not copy this code or run it in Canopy yet**.
```py
def row(inkSupply, size):
inkNeededForASquare = size * 4
# Not enough distance left to draw another square
if inkNeededForASquare > inkSupply:
return 0
else:
# Draw a single square
for i in range(4):
fd(size)
lt(90)
# Setup to draw next square
fd(size)
# Recursion
squareCount = row(inkSupply - inkNeededForASquare, size)
return squareCount + 1
```
Given the above function, your task is to sketch function call frames on the [provided worksheet](/content/labs/lab11/images/worksheet.pdf) for the following example invocations:
Example 1 to be drawn by Partner A:
```py
print row(300, 30) # ???
```
Example 2 to be drawn by Partner B:
```py
print row(60, 10) # ???
```
### Test your answers
Once your sketches are complete, paste the `row` function and invocations into your `lab11/part4.py` file and compare the computer's results against your own.
## Task 2. rowImproved
In this next task, we want to create an improved version of the row function that instead of just returning a single value (`squareCount`) it **returns a tuple** indicating how many squares were drawn *and* the total distance travelled by the Turtle/cursor.
__Capturing tuples returned from a function__
In order to complete this task, study the following example that demonstrates a function that returns a tuple...
```py
def pad(x, y, padding):
return x + padding, y + padding
```
Given the above code, make predictions of what the following print statements would produce:
```py
x, y = pad(300, 200, 10)
print x # ???
print y # ???
```
Run your code in Canopy to check your predictions. Note how the function `pad` returns a tuple. Because of this, we can capture its results in a tuple: `x, y = pad(300, 200, 10)`.
Once you understand the above code, copy and complete the following `rowImproved` function in your `lab11/part4.py` file:
```py
def rowImproved(inkSupply, size):
squareDistance = size * 4
# Not enough distance left to draw another square
if squareDistance > inkSupply:
return 0, 0
else:
# Draw a single square
for i in range(4):
fd(size)
lt(90)
# Setup to draw next square
fd(size)
# Recursion
??? = rowImproved(inkSupply - squareDistance, size)
return ???
```
Example invocations with expected results:
```py
print rowImproved(300, 30) # (2, 240)
print rowImproved(60, 10) # (1, 40)
```
__Important observation about the above function:__ Note how the base case also needed to return a tuple, `0,0`. It's essential that the value type returned by the base case is consistent with what is returned in the recursive case.
## Task 3. nestedSquares
Using the skills applied in Task 1 and 2, write a fruitful recursive function called `nestedSquares` returns a drawing of nested squares as shown in the examples below.
Parameters:
1. The **size** (length) of the square to be drawn
2. The **shrink factor** of the successive squares to be drawn
3. The **minimum sidelength** of a square; boxes will only draw a square if the side is greater than this minimum sidelength
4. The **color** of the Turtle's pen
Before writing any code, skim through the following examples and read the **hints** that follow.
#### Example A.
```py
nestedSquares(400, 0.2, 100, 'blue')
```
1 square, 1600 length (`400 * 4 sides = 1600`)
No more squares drawn because `400 * 0.2 = 80`, and 80 is less than the min sidelength of 100.
#### Example B.
`nestedSquares(400, 0.4, 100, 'magenta')`
2 squares, 2240 total length
```xml
1600 largest square (400 * 4 sides)
+ 640 small square (160 * 4 sides)
=====
2240 total length
```
#### Example C.
`nestedSquares(400, 0.75, 100, 'black')`
5 squares, 4881.25 total length
```xml
1600 (400 * 4 sides)
+ 1200 (300 * 4 sides)
+ 900 (225 * 4 sides)
+ 675 (168.75 * 4 sides)
+ 506.25 (126.5625 * 4 sides)
=========
4881.25 total length
```
#### Example D.
`nestedSquares(100, 0.8, 20, 'red')`
8 squares, 1664.45568 total length
```xml
400 (100 * 4 sides)
+ 320 (80 * 4 sides)
+ 256 (64 * 4 sides)
+ 204.8 (51.2 * 4 sides)
+ 163.84 (40.96 * 4 sides)
+ 131.072 (32.768 * 4 sides)
+ 104.8576 (26.2144 * 4 sides)
+ 83.88608 (20.97152 * 4 sides)
===========
1,664.45568 total length
```
### Hints
1. First, write the recursive function to produce the picture of nested squares. Relevant things to think about:
- When does the recursion end? Which parameter(s) determine if it is the base case?
- Handle the recursive case: draw one square and let recursion draw the remaining squares.
- Adjust the relevant parameters in the recursive call to ensure that the problem gets smaller each time.
2. After the above works, *then* add in the fruitful **counting of squares** only. You will need a variable to keep track of the square count, and you will need to return that value.
3. After the counting of squares works, *then* add the fruitful **sum of all the lengths** drawn. Each time the Turtle moves forward, keep track of that “mileage”.
There are hints in [Helpful Hints and Diagrams](/labs/lab11/hints) (see Table of Contents below), in particular, this [Turtle Hints diagram](/content/labs/lab11/hints/turtle-squares-design-patterns.png) may be helpful.
### Argh! My function doesn't work! Help!
Try some of these debugging tips:
Draw out the first few cases on paper, and make sure that you have broken down the problem correctly.
Additionally, add print statements at the start and end of your function to display each parameter value, e.g.
```py
print "nestedSquares(" + str(size) + str(shrink) + ... + ")"
```
This also helps you trace the recursion as it unfurls.
## Task 3. windows
Create a function called `windows` that produces the fruitful recursive square patterns shown below:
`windows(64, 0.4, 20, 'magenta')`
**3 boxes drawn, 460.8 total length**
```xml
256 (64 * 4 sides)
+ 102.4 (25.6 * 4 sides)
+ 102.4 (25.6 * 4 sides)
=======
460.8 total length
```
#### How to approach this design
**Do not use a `square` helper function in this task**— the squares in the pattern should be drawn as a side effect of moving the Turtle into position between recursive calls (as shown in the following video).
In order to do this, think of the fundamental piece of this design not as a single square, but as a corner of a square (repeated 2x via recursion to make a complete square).
Here's a video demonstrating this approach:
```py
windows(160, 0.4, 20, 'orange')
```
#### More examples
#### Example B.
`windows(160, 0.4, 20, 'magenta')`
**7 boxes drawn, 1561.6 total length**
#### Example C.
`windows(400, 0.4, 20, 'magenta')`
**15 boxes drawn, 4723.2 total length**
#### Example D.
`windows(400, 0.75, 100, 'black')`
**31 boxes drawn, 21100.0 total length**
## Task 5: Boxes (with clipped corners)
Write a fruitful recursive function called `boxes` that takes the following four parameters and produces squares in all four corners.
1. the **length** of the largest square
2. the **shrink factor** of the squares drawn at each of the four corners
3. the **length of an edge of the smallest outer box**
4. the **color** of the Turtle's pen
Once again, avoid approaching this design by trying to draw complete squares.
Instead, the fundamental pattern of the design can be broken down to a single side (repeated x4 via recursion to eventually make a square).
Here's a video demonstrating this approach:
```py
boxes(400, 0.4, 100, 'red')
```
#### Example A.
```py
boxes(400, 0.4, 100, 'magenta')
```
__Observations__
+ This example produces total of 5 boxes (1 outer box + 4 nested ones) and a total length of 4160.
+ The largest box, has side length of __400__.
+ In each corner, there is a smaller box drawn with a side length of __160__ (`400 * 0.4 = 160`).
+ There are no additional boxes drawn because the next set of corner boxes have a side length of 64 (`160 * 0.4 = 64`), which less than the smaller outer box length of __100__.
__Calculations__
```xml
2560 (4 smaller boxes with side length 160 x 4)
+ 1600 (1 outer box with side length 400 x 4)
==========
4160
```
#### Example B.
```py
boxes(400, 0.33, 30, 'magenta')
```
21 boxes, 6499.84 total length
Here's a diagram that shows the flow of how the recursive method boxes invokes itself (the first image is enlarged to show detail):
#### Example C.
```py
boxes(400, 0.25, 15, 'magenta')
```
21 boxes, 4800 total length
#### Example D.
```py
boxes(400, 0.4, 50, 'magenta')
```
21 boxes, 8256 total length
#### Example E.
```py
boxes(400, 0.44, 30, 'magenta')
```
85 boxes, 18095.0016 total length
#### Example F.
```py
boxes(400, 0.4, 10, 'magenta')
```
1365 boxes, 42072.576 total length
@include('/labs/lab11/_toc')
@stop
## Task 1. row
In last week's lab, we designed recursive Turtle functions that would draw a pattern a given number of times.
For example, when we invoked `row(3, 50)` it would draw **3** squares.
To make things more challenging, let's pretend the Turtle has a limited supply of ink. Instead of designing our function so that it repeats the design *X* number of times, let's limit it by how much “ink” is left.
Each pixel travelled represents a “drop of ink”. E.g. if the turtle moves `fd(30)` that's 30 hypothetical drops of ink. Thus, to complete a square, it would require 120 drops of ink (30 * 4).
In addition to limiting the distance travelled, we also want to find out **how many squares were drawn** with the given limit. I.e. we want to make the row function fruitful.
The following is the solution to this function. **Do not copy this code or run it in Canopy yet**.
```py
def row(inkSupply, size):
inkNeededForASquare = size * 4
# Not enough distance left to draw another square
if inkNeededForASquare > inkSupply:
return 0
else:
# Draw a single square
for i in range(4):
fd(size)
lt(90)
# Setup to draw next square
fd(size)
# Recursion
squareCount = row(inkSupply - inkNeededForASquare, size)
return squareCount + 1
```
Given the above function, your task is to sketch function call frames on the [provided worksheet](/content/labs/lab11/images/worksheet.pdf) for the following example invocations:
Example 1 to be drawn by Partner A:
```py
print row(300, 30) # ???
```
Example 2 to be drawn by Partner B:
```py
print row(60, 10) # ???
```
### Test your answers
Once your sketches are complete, paste the `row` function and invocations into your `lab11/part4.py` file and compare the computer's results against your own.
## Task 2. rowImproved
In this next task, we want to create an improved version of the row function that instead of just returning a single value (`squareCount`) it **returns a tuple** indicating how many squares were drawn *and* the total distance travelled by the Turtle/cursor.
1 square, 1600 length (`400 * 4 sides = 1600`)
No more squares drawn because `400 * 0.2 = 80`, and 80 is less than the min sidelength of 100.
#### Example B.
`nestedSquares(400, 0.4, 100, 'magenta')`
2 squares, 2240 total length
```xml
1600 largest square (400 * 4 sides)
+ 640 small square (160 * 4 sides)
=====
2240 total length
```
#### Example C.
`nestedSquares(400, 0.75, 100, 'black')`
5 squares, 4881.25 total length
```xml
1600 (400 * 4 sides)
+ 1200 (300 * 4 sides)
+ 900 (225 * 4 sides)
+ 675 (168.75 * 4 sides)
+ 506.25 (126.5625 * 4 sides)
=========
4881.25 total length
```
#### Example D.
`nestedSquares(100, 0.8, 20, 'red')`
8 squares, 1664.45568 total length
```xml
400 (100 * 4 sides)
+ 320 (80 * 4 sides)
+ 256 (64 * 4 sides)
+ 204.8 (51.2 * 4 sides)
+ 163.84 (40.96 * 4 sides)
+ 131.072 (32.768 * 4 sides)
+ 104.8576 (26.2144 * 4 sides)
+ 83.88608 (20.97152 * 4 sides)
===========
1,664.45568 total length
```
### Hints
1. First, write the recursive function to produce the picture of nested squares. Relevant things to think about:
- When does the recursion end? Which parameter(s) determine if it is the base case?
- Handle the recursive case: draw one square and let recursion draw the remaining squares.
- Adjust the relevant parameters in the recursive call to ensure that the problem gets smaller each time.
2. After the above works, *then* add in the fruitful **counting of squares** only. You will need a variable to keep track of the square count, and you will need to return that value.
3. After the counting of squares works, *then* add the fruitful **sum of all the lengths** drawn. Each time the Turtle moves forward, keep track of that “mileage”.
There are hints in [Helpful Hints and Diagrams](/labs/lab11/hints) (see Table of Contents below), in particular, this [Turtle Hints diagram](/content/labs/lab11/hints/turtle-squares-design-patterns.png) may be helpful.
### 
Argh! My function doesn't work! Help!
Try some of these debugging tips:
**3 boxes drawn, 460.8 total length**
```xml
256 (64 * 4 sides)
+ 102.4 (25.6 * 4 sides)
+ 102.4 (25.6 * 4 sides)
=======
460.8 total length
```
#### How to approach this design
**Do not use a `square` helper function in this task**— the squares in the pattern should be drawn as a side effect of moving the Turtle into position between recursive calls (as shown in the following video).
In order to do this, think of the fundamental piece of this design not as a single square, but as a corner of a square (repeated 2x via recursion to make a complete square).
Here's a video demonstrating this approach:
```py
windows(160, 0.4, 20, 'orange')
```
#### More examples
#### Example B.
`windows(160, 0.4, 20, 'magenta')`
**7 boxes drawn, 1561.6 total length**
#### Example C.
`windows(400, 0.4, 20, 'magenta')`
**15 boxes drawn, 4723.2 total length**
#### Example D.
`windows(400, 0.75, 100, 'black')`
**31 boxes drawn, 21100.0 total length**
## Task 5: Boxes (with clipped corners)
Write a fruitful recursive function called `boxes` that takes the following four parameters and produces squares in all four corners.
1. the **length** of the largest square
2. the **shrink factor** of the squares drawn at each of the four corners
3. the **length of an edge of the smallest outer box**
4. the **color** of the Turtle's pen
__Observations__
+ This example produces total of 5 boxes (1 outer box + 4 nested ones) and a total length of 4160.
+ The largest box, has side length of __400__.
+ In each corner, there is a smaller box drawn with a side length of __160__ (`400 * 0.4 = 160`).
+ There are no additional boxes drawn because the next set of corner boxes have a side length of 64 (`160 * 0.4 = 64`), which less than the smaller outer box length of __100__.
__Calculations__
```xml
2560 (4 smaller boxes with side length 160 x 4)
+ 1600 (1 outer box with side length 400 x 4)
==========
4160
```
#### Example B.
```py
boxes(400, 0.33, 30, 'magenta')
```
21 boxes, 6499.84 total length
Here's a diagram that shows the flow of how the recursive method boxes invokes itself (the first image is enlarged to show detail):
#### Example C.
```py
boxes(400, 0.25, 15, 'magenta')
```
21 boxes, 4800 total length
#### Example D.
```py
boxes(400, 0.4, 50, 'magenta')
```
21 boxes, 8256 total length
#### Example E.
```py
boxes(400, 0.44, 30, 'magenta')
```
85 boxes, 18095.0016 total length
#### Example F.
```py
boxes(400, 0.4, 10, 'magenta')
```
1365 boxes, 42072.576 total length
@include('/labs/lab11/_toc')
@stop