Table of Contents
polygonpolyflowspiralBack (Invariance)zigzag function to become invariantsumUpfactorialpolygon¶Loops can be used in conjunction with turtles to make interesting designs.
Write the function polygon, which will produce different shapes as shown in the slides.
from turtle import *
def polygon(numSides, sideLength):
'''Draws a polygon with the specified number
of sides, each with the specified length.
'''
# Your code here
for _ in range(numSides):
fd(sideLength)
rt(360.0/numSides)
# Draw a triangle
polygon(3, 100)
# Draw a square, reset canvas first
reset()
polygon(4, 100)
# Draw a pentagon, reset canvas first
reset()
polygon(5, 75)
# Draw an approximate circle, reset canvas first
reset()
polygon(100, 3)
polyflow¶In addition to the simple shapes we saw above, with loops we can create more interesting shapes too,
such as geometric flowers. Examples are shown in the slides.
Use the helper function polygon that you defined in Exercise 1 to write poloyflow.
def polyFlow(numPetals, petalSides, petalLen):
'''Draws "flowers" with numPetals arranged around
a center point. Each petal is a polygon with
petalSides sides of length petalLen.
'''
# Your code here
for petal in range(numPetals):
polygon(petalSides, petalLen)
rt(360.0/numPetals)
# Example 1: square petals
reset()
speed(10)
polyFlow(7, 4, 80)
# Example 2: pentagon petals
reset()
speed(10)
polyFlow(10, 5, 75)
# Example 3: hexagon petals
reset()
speed(10)
polyFlow(11, 6, 60)
Let's try to write together the recursive function spiral, which creates the images shown in the slides.
def spiral(sideLen, angle, scaleFactor, minLength):
'''
Recursively creates a spiral, takes these parameters:
1. sideLen is the length of the current side;
2. angle is the amount the turtle turns left to draw the next side;
3. scaleFactor is the multiplicative factor by which to scale the next side
(it is between 0.0 and 1.0);
4. minLength is the smallest side length that the turtle will draw.
'''
if sideLen >= minLength:
fd(sideLen)
lt(angle)
spiral(sideLen*scaleFactor, angle, scaleFactor, minLength)
To test the function with large values, we need to move the turtle from (0,0) in the center
of the canvas to some other point. However, whenever the turtle moves, it leaves a trail behind.
This is why we used the methods pu and pd (pen up and pen down).
To keep everything clean, we'll wrap it all in the function.
def drawSpiral(sideLen, angle, scaleFactor, minLength):
"""Helper function to prepare the window for drawing and
then calling the spiral function.
"""
reset()
padding = 200
width = sideLen + padding
height = sideLen + padding
setup(width, height, 0, 0)
pu()
goto(-height/2+padding/2, -width/2+padding/2)
pd()
spiral(sideLen, angle, scaleFactor, minLength)
#exitonclick()
drawSpiral(625, 90, 0.7, 100)
Let's see the examples shown in slides:
drawSpiral(200, 90, 0.9, 10)
drawSpiral(200, 72, 0.97, 10)
drawSpiral(200, 121, 0.95, 15)
spiralBack (Invariance)¶A function is invariant relative to an object’s state if the state of the object is the same
before and after the function is invoked.
Let's write the following function together. It's very similar to spiral, we just need to
undo the operations we did before the recursion.
def spiralBack(sideLen, angle, scaleFactor, minLength):
'''Draws a spiral. The state of the turtle (position,
direction) after drawing the spiral should be the
same as before drawing the spiral.
'''
# Your code here
if sideLen >= minLength:
fd(sideLen)
lt(angle)
spiralBack(sideLen*scaleFactor, angle, scaleFactor, minLength)
rt(angle)
bk(sideLen)
reset()
spiralBack(200, 95, 0.93, 10)
zigzag function to become invariant¶This is another exercise to illustrate the concept of invariance. First run the code to see what it does, and then modify it so that the turtle returns to the center, where it started.
def zigzag(num, length):
'''Draws the specified number of zigzags with the specified length.'''
if num>0:
lt(45)
fd(length)
rt(90)
fd(length*2)
lt(90)
fd(length)
rt(45)
zigzag(num-1, length)
# Your code here
lt(45)
bk(length)
rt(90)
bk(length*2)
lt(90)
bk(length)
rt(45)
reset()
zigzag(5, 20)
The previous exercises showed invariance in the context of turtle spirals. Now we will use the idea of invariant functions to create more sophisticated turtle designs, again using recursion. The lecture slides show some designs created with the trees recursive function.
def tree(levels, trunkLen, angle, shrinkFactor):
'''Draws recursively a tree design with the following parameters:
1. levels is the number of branches on any path from the root to a leaf
2. trunkLen is the length of the base trunk of the tree
3. angle is the angle from the trunk for each subtree
4. shrinkFactor is the shrinking factor for each subtree.
'''
if levels > 0:
# Draw the trunk.
fd(trunkLen)
# Turn and draw the right subtree.
rt(angle)
tree(levels-1, trunkLen*shrinkFactor, angle, shrinkFactor)
# Turn and draw the left subtree.
lt(angle * 2)
tree(levels-1, trunkLen*shrinkFactor, angle, shrinkFactor)
# Turn back and back up to root without drawing.
rt(angle)
pu()
bk(trunkLen)
pd()
Let's try the tree from the slides:
reset()
lt(90) # Face north first to grow the tree upwards
tree(3, 60, 45, 0.6)
Let's create a more sophisticated tree:
reset()
lt(90) # Face north first to grow the tree upwards
speed(20)
tree(7, 75, 30, 0.8)
Yet another sophisticated tree:
reset()
lt(90) # Face north first to grow the tree upwards
speed(20)
tree(10, 80, 45, 0.7)
The function tree creates symmetric, perfect trees that don't resemble natural trees. Can we do better? Yes, by introducing randomness.
Run the code below and then study how it works.
import random
def treeRandom(trunkLen, minLength, thickness, minThickness,
minAngle, maxAngle, minShrink, maxShrink):
if (trunkLen < minLength) or (thickness < minThickness): # Base case
pass # Do nothing
else:
angle1 = random.uniform(minAngle, maxAngle)
angle2 = random.uniform(minAngle, maxAngle)
shrink1 = random.uniform(minShrink, maxShrink)
shrink2 = random.uniform(minShrink, maxShrink)
pensize(thickness)
fd(trunkLen)
rt(angle1)
treeRandom(trunkLen*shrink1, minLength, thickness*shrink1,
minThickness, minAngle, maxAngle, minShrink, maxShrink)
lt(angle1 + angle2)
treeRandom(trunkLen*shrink2, minLength, thickness*shrink2,
minThickness, minAngle, maxAngle, minShrink, maxShrink)
rt(angle2)
pensize(thickness)
bk(trunkLen)
reset()
speed(10)
lt(90) # Face north first to grow the tree upwards
treeRandom(120, 3, 20, 1, 15, 55, 0.5, 0.8)
def countUp(n):
if n <= 0:
pass
else:
countUp(n-1)
print(n)
countUp(5)
How would we write a function to return the sum of numbers from 1 up to n?
We can do this by returning a value from the recursive function instead of printing the numbers.
def sumUp(n):
"""Returns sum of integers from 1 up to n"""
if n <= 0:
return 0
else:
return n + sumUp(n - 1)
print('The sum from 1 up to 5 is', sumUp(5))
It never hurts to name the subResult of the recursive call and the result of the whole call (and often helps you think about what's going on)
def sumUp(n):
"""Returns sum of integers from 1 up to n"""
if n <= 0:
return 0
else:
subResult = sumUp(n-1) # Result returned by recursive call
result = n + subResult # Result for whole call
return result
print('The sum from 1 up to 5 is', sumUp(5))
Often things will go wrong, and your recursive function is not doing what you expect it to do.
Use debugging techniques to figure out what is going on. In Python, you can add print statements in the function body to do that.
Add such statements everywere there might be the opportunity to make a mistake:
You can see this in action, with the following version of sumUpDebugging(n), which contains three debugging print statements.
def sumUpDebugging(n):
"""sumUp with debugging statements."""
print(f'entering sumUp({n})')
if n == 0:
print('sumUp(0) returns 0')
return 0
else:
subResult = sumUpDebugging(n-1)
result = n + subResult
print(f'sumUp({n}) returns {result}')
return result
sumUpDebugging(5)
We can even add an extra prefix arg to track how "deep" we are in the recursion
def sumUpDebuggingWithPrefix(prefix, n):
"""sumUp with extra string arg and debugging statements."""
print(f'{prefix} entering sumUp({n})')
if n == 0:
print(f'{prefix} sumUp(0) returns 0')
return 0
else:
subResult = sumUpDebuggingWithPrefix(prefix + '| ', n-1)
result = n + subResult
print(f'{prefix} sumUp({n}) returns {result}')
return result
sumUpDebuggingWithPrefix('', 5)
How many ways can you arrange 3 items in a sequence? How about 4?
The general answer is given by factorial(n), often denoted in math as $n!$. It is given by the formula:
$$n! = n * (n-1) * (n-2) *(n -3) * \ldots 2 * 1$$
Your Turn: Try writing a function factorial that computes the factorial of n without any loops, using the same logic as sumUp.
def factorial(n):
"""Returns n! using recursion"""
# Your code here
# Base case
if n <= 0:
return 1 # the identity value in multiplication
else:
return n * factorial(n-1)
print('5! is', factorial(5))
Define the koch and snowflake functions as indicated on the slides.
HINT: The koch function does work in its base case. It also calls itself several times in the recursive case.
def koch(levels, size):
# Your code here
if levels == 0:
fd(size)
else:
koch(levels-1, size/3.0)
lt(60)
koch(levels-1, size/3.0)
rt(120)
koch(levels-1, size/3.0)
lt(60)
koch(levels-1, size/3.0)
# Invoke the function
reset()
speed(20)
koch(3, 250)
Once you write the function koch, writing snowflake is really simple.
This is because snowflake is not a recursive function. It simply calls the function koch that is recursive.
def snowflake(levels, size):
# Your code here
for i in range(3):
koch(levels, size)
rt(120)
# invoke the function
reset()
speed(20)
snowflake(3, 250)
This is all for today's lecture!