Table of Content
spiralLength
spiralCount
spiralTuple
branchCount
countDownListPrintResults
countUpList
sublistSum
functionsublistSum
sublists
fibRec
fibLoop
spiralLength
¶First some housekeeping function to setup the turtle drawing:
from turtle import *
setup(600, 600, 0, 0)
def resetTurtle():
reset()
pu()
goto(-250, -250)
pd()
The function spiralLength
below modifies the function spiralBack
that we covered in the previous lecture so that it returns the total length of lines in the spiral.
def spiralLength(sideLen, angle, scaleFactor, minLength):
"""Draws a spiral based on the given parameters and leaves the turtle's location
and orientation invariant. Also returns the total length of lines in the spiral.
"""
if sideLen < minLength:
return 0
else:
fd(sideLen); lt(angle) # Put two statements on one line with semi-colon
subLen = spiralLength(sideLen*scaleFactor,
angle,
scaleFactor,
minLength)
rt(angle); bk(sideLen)
return sideLen + subLen
Invoke the function:
resetTurtle()
totalLen = spiralLength(100, 90, 0.5, 5)
print("The total length of the spiral is", totalLen)
The total length of the spiral is 193.75
spiralCount
¶Below we have copied spiralLength
and modified it to be named spiralCount
. The goal is to specify what should go in the return statements, so that the function returns the number of lines in the spiral.
def spiralCount(sideLen, angle, scaleFactor, minLength):
"""Draws a spiral based on the given parameters and leaves the turtle's location
and orientation invariant. Also returns the number lines in the spiral.
"""
if sideLen < minLength:
# Add the return statement
# Your code here
return 0
else:
fd(sideLen); lt(angle) # Put two statements on one line with semi-colon
subCount = spiralCount(sideLen*scaleFactor,
angle,
scaleFactor,
minLength)
rt(angle); bk(sideLen)
# Add the return statement
# Your code here
return 1 + subCount
Invoke the function:
resetTurtle()
totalCount = spiralCount(100, 90, 0.5, 5)
print("The number of lines in the spiral is", totalCount)
The number of lines in the spiral is 5
spiralTuple
¶Now, copy below your working version of spiralLength
and modify it to be a function spiralTuple
that returns a pair (i.e., a 2-tuple) of:
def spiralTuple(sideLen, angle, scaleFactor, minLength):
"""Draws a spiral based on the given parameters and leaves the turtle's
location and orientation invariant. Also returns a pair (2-tuple) of
(1) the length of lines in the spiral
(2) the number of lines in the spiral.
"""
# Your code here
if sideLen < minLength:
return (0, 0)
else:
fd(sideLen); lt(angle) # Put two statements on one line with semi-colon
subLen, subCount = spiralTuple(sideLen*scaleFactor,
angle,
scaleFactor,
minLength)
rt(angle); bk(sideLen)
return sideLen + subLen, 1 + subCount
Invoke the function:
resetTurtle()
(totalLength, totalCount) = spiralTuple(512, 90, 0.5, 5)
print(f"The spiral has {totalCount} lines whose total length is {totalLength}")
The spiral has 7 lines whose total length is 1016.0
branchCount
¶Similarly to the modifications that we did to functions that draw spirals, we can modify the function that draws trees to become a fruitful function, to count the number of branches that are drawn.
Below is the original tree
function for drawing a tree:
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:
pass
else:
# 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()
Copy and modify the solution of tree
so that it becomes branchCount
, which in addition to drawing the tree also returns the number of all branches in the tree.
Note: Don't forget to change the function name in the recursive calls from tree
to branchCount
when you paste the solution in the cell below.
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)
# Keep track of branches for the right subtree
branchCount1 = branchCount(levels-1, trunkLen*shrinkFactor, angle, shrinkFactor)
# Turn and draw the left subtree.
lt(angle * 2)
# Keep track of branches for the left subtree
branchCount2 = branchCount(levels-1, trunkLen*shrinkFactor, angle, shrinkFactor)
# Turn back and back up to root without drawing.
rt(angle)
pu()
bk(trunkLen)
pd()
return 1 + branchCount1 + branchCount2
Let's draw a small tree with level 3:
reset()
lt(90) # Face north first to grow the tree upwards
print(f"The number of branches drawn is {branchCount(3, 60, 45, 0.6)}")
The number of branches drawn is 7
Let's draw a bigger tree with level 7:
reset()
lt(90) # Face north first to grow the tree upwards
speed(20)
print(f"The number of branches drawn is {branchCount(7, 75, 30, 0.8)}")
The number of branches drawn is 127
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]
print('countUpList(8) returns', countUpList(8))
countUpList(8) returns [1, 2, 3, 4, 5, 6, 7, 8]
For a given list L (possibly containing duplicates), we will use the term sublist of L to refer to any list that keeps some elements of L and omits others in their same relative order. E.g., the sublists of [5, 3, 8, 3] are:
[5, 3, 8, 3] # Keep all elements
[3, 8, 3] # Omit 5
[5, 8, 3] # Omit 1st 3
[5, 3, 3] # Omit 8
[5, 3, 8] # Omit 2nd 3
[8, 3] # Omit 5 and 1st 3
[3, 3] # Omit 5 and 8
[3, 8] # Omit 5 and 2nd 3
[5, 3] # Omit 8 and 1st 3
[5, 3] # Omit 8 and 2nd 3 # (Note duplication)
[5, 8] # Omit both 3s
[5] # Keep only 5
[3] # Keep only 1st 3
[8] # Keep only 8
[3] # Keep only 2nd 3 # (Note duplication)
[] # Omit all elements
In the following we will look at a few different examples using sublists. You will also write your own function to create all sublists of a list, recursively.
sublistSum
function¶Given a list of numbers (possibly containing duplicates) and a target number, sublistSum
returns a list of all sublists whose sum is the target number. For example:
sublistSum([2, 3, 5, 5, 11, 17], 23) --> [[2, 5, 5, 11]]
sublistSum([2, 3, 5, 5, 11, 17], 30) --> [[2, 11, 17], [3, 5, 5, 17]]
sublistSum([2, 3, 5, 5, 11, 17], 24) --> [[2, 5, 17], [2, 5, 17], [3, 5, 5, 11]]
sublistSum([2, 3, 5, 5, 11, 17], 34) --> []
Note: More details about these results and how sublistSum
works are given in the lecture slides.
def sublistSum(nums, target):
'''Assume nums is a list of numbers. Return a list of all sublists of nums
whose numbers sum to target. If nums contains duplicates,
there might be duplicate sublists in the result.
This implementation does not use sublists (see below) as a helper function,
and instead does a recursion directly.
'''
if nums == []: # base case
# Subtlety: there are *two* sub base cases:
if target == 0:
return [[]] # sum([]) == 0, so include [] in result list
else:
return [] # sum([]) cannot be a nonzero target,
# so don't include [] in result
else:
fst = nums[0] # first number in list
rst = nums[1:] # rest of numbers in list
keepingFirst = [([fst] + sumList) # all sublists keeping fst
for sumList in sublistSum(rst, target-fst)
# recursive call excludes fst
]
omittingFirst = sublistSum(rst, target) # all sublsts omitting fst
return keepingFirst + omittingFirst
To test the function, we will write a helper function:
def testSublistSum(nums, target):
'''Helper function to test the function sublist'''
print(f'sublistSum({nums}, {target}) => {sublistSum(nums,target)}')
Now we can call the testSublistSum
many times to test sublistSum
:
for tgt in range(20,36):
testSublistSum([2, 3, 5, 5, 11, 17], tgt)
sublistSum([2, 3, 5, 5, 11, 17], 20) => [[3, 17]] sublistSum([2, 3, 5, 5, 11, 17], 21) => [[2, 3, 5, 11], [2, 3, 5, 11], [5, 5, 11]] sublistSum([2, 3, 5, 5, 11, 17], 22) => [[2, 3, 17], [5, 17], [5, 17]] sublistSum([2, 3, 5, 5, 11, 17], 23) => [[2, 5, 5, 11]] sublistSum([2, 3, 5, 5, 11, 17], 24) => [[2, 5, 17], [2, 5, 17], [3, 5, 5, 11]] sublistSum([2, 3, 5, 5, 11, 17], 25) => [[3, 5, 17], [3, 5, 17]] sublistSum([2, 3, 5, 5, 11, 17], 26) => [[2, 3, 5, 5, 11]] sublistSum([2, 3, 5, 5, 11, 17], 27) => [[2, 3, 5, 17], [2, 3, 5, 17], [5, 5, 17]] sublistSum([2, 3, 5, 5, 11, 17], 28) => [[11, 17]] sublistSum([2, 3, 5, 5, 11, 17], 29) => [[2, 5, 5, 17]] sublistSum([2, 3, 5, 5, 11, 17], 30) => [[2, 11, 17], [3, 5, 5, 17]] sublistSum([2, 3, 5, 5, 11, 17], 31) => [[3, 11, 17]] sublistSum([2, 3, 5, 5, 11, 17], 32) => [[2, 3, 5, 5, 17]] sublistSum([2, 3, 5, 5, 11, 17], 33) => [[2, 3, 11, 17], [5, 11, 17], [5, 11, 17]] sublistSum([2, 3, 5, 5, 11, 17], 34) => [] sublistSum([2, 3, 5, 5, 11, 17], 35) => [[2, 5, 11, 17], [2, 5, 11, 17]]
sublistSum
¶Suppose we had a sublists
function that returns all sublists of a list.
E.g.:
sublists([5, 3, 5, 8])
--> [[5, 3, 5, 8], [5, 3, 5], [5, 3, 8], [5, 3],
[5, 5, 8], [5, 5], [5, 8], [5],
[3, 5, 8], [3, 5], [3, 8], [3],
[5, 8], [5], [8], []]
Then we could define sublistSum
as:
def sublistSum(nums, target):
"""Alternative implemenation of sublistSum using the recursive
function sublists and list comprehension.
"""
return [ns for ns in sublists(nums) if sum(ns) == target]
In the next exercise, you'll help complete the definition of sublists
and then test this new solutions for sublistSum
.
sublists
¶You are given the almost complete body of the function sublists
. Your task is to fill in the skeleton of the function that is provided in Slide 19 of today's lecture.
def sublists(xs):
'''Given a list of n values (which might contain duplicates),
return a list of all possible 2^n sublists, where a sublist is
the result of independently choosing to keep or not keep
particular value occurrences without changing their relative order.
The order of sublists is not specified.
E.g., one ordering of the sublists of [3,1,2] is
[ [], [2], [1], [1, 2], [3], [3, 2], [3, 1], [3, 1, 2] ]
When the given lists contains duplicates, there will can be duplicate
sublists. e.g. one ordering of the sublists of [1, 3,1,2] is
[[], [2], [1], [1, 2], [3], [3, 2], [3, 1], [3, 1, 2],
[1], [1, 2], [1, 1], [1, 1, 2], [1, 3], [1, 3, 2], [1, 3, 1], [1, 3, 1, 2]]
in which the sublists [1,2] and [1] each appear twice.
'''
# Your code here
if xs == []:
return [[]]
else:
fst = xs[0]
rst = xs[1:]
omittingFirst = sublists(rst)
keepingFirst = [[fst] + sublist for sublist in omittingFirst]
return keepingFirst + omittingFirst
Let's invoke the function a couple of times with different lists:
sublists([3,1,2])
[[3, 1, 2], [3, 1], [3, 2], [3], [1, 2], [1], [2], []]
sublists([1,3,1,2])
[[1, 3, 1, 2], [1, 3, 1], [1, 3, 2], [1, 3], [1, 1, 2], [1, 1], [1, 2], [1], [3, 1, 2], [3, 1], [3, 2], [3], [1, 2], [1], [2], []]
We can now test the alternative sublistSum
as well, but first let's put here its definition:
def sublistSum(nums, target):
"""Alternative implemenation of sublistSum using the recursive
function sublists and list comprehension.
"""
return [ns for ns in sublists(nums) if sum(ns) == target]
Here are some tests:
sublistSum([2, 3, 5, 5, 11, 17], 20)
[[3, 17]]
sublistSum([2, 3, 5, 5, 11, 17], 24)
[[2, 5, 17], [2, 5, 17], [3, 5, 5, 11]]
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 month
Below you will first write a recursive implementation of the Fibonacci numbers and then an iterative one.
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)
Let's test the function by trying to find the 5th, 10th, 15th, ..., up to the 35th number in the Fibonacci sequence:
timedResults = [timedFibRec(n) for n in range(5,36,5)]
for result in timedResults:
print(result)
(5, 4.0531158447265625e-06, 5) (10, 2.7894973754882812e-05, 55) (15, 0.0002980232238769531, 610) (20, 0.0032711029052734375, 6765) (25, 0.034362077713012695, 75025) (30, 0.2772939205169678, 832040) (35, 3.1290528774261475, 9227465)
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!
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
Let's run some tests:
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
Did you notice how fast these function invocations were?
This is the end of the notebook!