Once again we will use turtle graphics to solve interesting recursion problems. First import the turtle module.
from turtle import *
Last time we look at 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 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, the one that is in the cover page of the slides:
reset()
lt(90) # Face north first to grow the tree upwards
tree(7, 75, 30, 0.8)
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()
lt(90) # Face north first to grow the tree upwards
treeRandom(120, 3, 20, 1, 15, 55, 0.5, 0.8)
Let's apply our concepts of invariance, trees, and fruitful recursion into one example. Using our function tree from above draw the same tree but also return a count of all the branches drawn.
def branchCount(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.
'''
# Your code here
if levels <= 0:
return 0
else:
# Draw the trunk.
fd(trunkLen)
# Turn and draw the right subtree.
rt(angle)
branchCount1 = branchCount(levels-1, trunkLen*shrinkFactor, angle, shrinkFactor)
# Turn and draw the left subtree.
lt(angle * 2)
branchCount2 = branchCount(levels-1, trunkLen*shrinkFactor, angle, shrinkFactor)
# Turn back and back up to root without drawing.
rt(angle)
pu()
bk(trunkLen)
pd()
return branchCount1 + branchCount2 + 1
reset()
lt(90) # Face north first to grow the tree upwards
print("The number of branches drawn is {}".format(branchCount(3, 60, 45, 0.6)))
The number of branches drawn is 7
reset()
lt(90) # Face north first to grow the tree upwards
print("The number of branches drawn is {}".format(branchCount(7, 75, 30, 0.8)))
The number of branches drawn is 127
zigzag function to become invariant¶This is another exercise to help work on 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.'''
# Your code here
if num>0:
lt(45)
fd(length)
rt(90)
fd(length*2)
lt(90)
fd(length)
rt(45)
zigzag(num-1, length)
# add your code here to undo the pre-recursion actions
lt(45)
bk(length)
rt(90)
bk(length*2)
lt(90)
bk(length)
rt(45)
reset()
zigzag(5, 20)
Define the koch and snowflake functions as indicated on the slides.
HINT: This 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
reset()
koch(3, 150)
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):
# define this function
# it calls the function koch above - no need for recursion
# Your code here
for i in range(3):
koch(levels, size)
rt(120)
#invoke
reset()
speed(20)
snowflake(0, 150)
We have seen recursion in the context of printing and adding numbers with countUp and sumUp, respectively. Here is a function that creates a list of numbers from n to 1.
def countDownList(n):
"""Returns a list of numbers from n down to 1.
For example, countDownList(5) returns [5,4,3,2,1].
"""
if n <= 0:
return []
else:
return [n] + countDownList(n-1)
print('countDownList(8) returns', countDownList(8))
countDownList(8) returns [8, 7, 6, 5, 4, 3, 2, 1]
countDownListPrintResults¶Modify countDownList to be the function countDownListPrintResults that prints out the list returned by each recursive call. For example:
In[]: countDownListPrintResults(5)
[]
[1]
[2, 1]
[3, 2, 1]
[4, 3, 2, 1]
[5, 4, 3, 2, 1]
Out[]:
[5, 4, 3, 2, 1]
def countDownListPrintResults(n):
"""Behaves like countDownList that additionally prints out
intermediary results.
"""
# Your code here
if n <= 0:
print([])
return [] # base case returns empty list
else:
cntDwnList = [n] + countDownListPrintResults(n-1)
print(cntDwnList)
return cntDwnList
countDownListPrintResults(5)
[] [1] [2, 1] [3, 2, 1] [4, 3, 2, 1] [5, 4, 3, 2, 1]
[5, 4, 3, 2, 1]
countUpList¶Write a new function countUpList, which returns a list of integers from 1 up to n.
You will only need to change one thing in countDownList to get countUpList.
def countUpList(n):
"""Returns a list of integers from n up to 1.
For example, for n=5, the returned value is [1, 2, 3, 4, 5].
"""
# Your code here
if n <= 0:
return []
else:
return countUpList(n-1) + [n]
countUpList(8)
[1, 2, 3, 4, 5, 6, 7, 8]
countUpList(5)
[1, 2, 3, 4, 5]
Fibonacci numbers model the number of pairs of rabbits in a given month, assuming:
This leads to the following recursive formula for the nth Fibonacci number fib(n):
fib(0) = 0 ; no pairs initially
fib(1) = 1 ; 1 pair introduced the first month
fib(n) = fib(n-1) ; pairs never die, so live to next month
+ fib(n-2) ; all sexually mature pairs produce a pair each monthfibRec¶Write the function fibRec that will calculate the nth Fibonacci number recursively.
def fibRec(n):
"""Returns the nth Fibonacci number."""
# Your code here
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibRec(n-1) + fibRec(n-2)
print('fibRec(6) is', fibRec(6))
print('fibRec(10) is', fibRec(10))
fibRec(6) is 8 fibRec(10) is 55
How long does it take to calculate fibRec(n)? Let's look at the time (in seconds) to calculate some values.
import time
def timedFibRec(n):
"""Helper function that measures elapsed time for a function call."""
start = time.time()
result = fibRec(n)
end = time.time()
timeTaken = end - start
return (n, timeTaken, result)
timedResults = [timedFibRec(n) for n in range(5,36,5)]
for result in timedResults:
print(result)
(5, 5.9604644775390625e-06, 5) (10, 3.2901763916015625e-05, 55) (15, 0.0003561973571777344, 610) (20, 0.005563974380493164, 6765) (25, 0.04692697525024414, 75025) (30, 0.3556549549102783, 832040) (35, 3.844244956970215, 9227465)
What's the ratio of the time for fib(n+5) to fib(n) for the above examples?
[resultsPair[1][1]/resultsPair[0][1] for resultsPair in zip(timedResults, timedResults[1:])]
[5.52, 10.826086956521738, 15.620481927710843, 8.434074645412863, 7.578902177557843, 10.80891719318239]
Based on the above, estimate how long it will take to calculate fibRec(100). (Note that there are about 3 x 10^7 seconds in a year.)
The answer is approximately 4.3 million years.
fibLoop¶Here is an iterative way to view Fibonacci numbers: the Fibonacci sequence starts with 0 and 1, and each successive number is the sum of the previous two:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...The nth Fibonacci number is the value corresponding at the nth index. So fib(0) is 0, fib(1) is 1, fib(2) is 1, fib(3) is 2, etc.
Based on this perspective, Fibonacci numbers can be calculated efficiently via a loop!
# enter your solution for a looping fibonacci
# HINT: it helps to use simultaneous tuple assignment
def fibLoop(n):
"""Returns the nth Fibonacci number."""
# Your code here
fibi = 0
fibi_next = 1
for i in range(1, n+1):
fibi, fibi_next = fibi_next, fibi+fibi_next
return fibi
print('fibLoop(6) is', fibLoop(6))
print('fibLoop(10) is', fibLoop(10))
print('fibLoop(40) is', fibLoop(40))
print('fibLoop(50) is', fibLoop(50))
print('fibLoop(100) is', fibLoop(100))
fibLoop(6) is 8 fibLoop(10) is 55 fibLoop(40) is 102334155 fibLoop(50) is 12586269025 fibLoop(100) is 354224848179261915075