Table of Contents
Recall the countUp function to print numbers from 1 up to n:
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))
Note: 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)
Last time we wrote the recursive function spiral, which creates the images shown in the slides.
from turtle import *
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 = 100
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)
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.
The function spiralBack that we discussed last time is an example of invariant function:
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.
'''
if sideLen >= minLength:
fd(sideLen)
lt(angle)
spiralBack(sideLen*scaleFactor, angle, scaleFactor, minLength)
rt(angle)
bk(sideLen)
reset()
spiralBack(200, 95, 0.8, 40)
spiralLength¶Run this code below to setup the screen and turtle for the next series of exercises. Run just once!
setup(600, 600, 0, 0)
def resetTurtle():
reset()
pu()
goto(-250, -250)
pd()
We can apply our new knowledge of fruitful recursion to our turtle spiral example. Modify the spiralBack function to be a spiralLength function that returns the total length of the lines in the spiral in addition to drawing the spiral and bringing the turtle back to its initial location and orientation.
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.
"""
# Your code here
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
resetTurtle()
totalLen = spiralLength(100, 90, 0.5, 5)
print("The total length of the spiral is", totalLen)
spiralCount¶Now, copy below your working version of spiralLength and modify it to be a function spiralCount that 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.
"""
# Your code here
if sideLen < minLength:
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)
return 1 + subCount
resetTurtle()
totalCount = spiralCount(100, 90, 0.5, 5)
print("The number of lines in the spiral is", totalCount)
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
resetTurtle()
(totalLength, totalCount) = spiralTuple(512, 90, 0.5, 5)
print("The spiral has", totalCount, "lines whose total length is", totalLength)
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)}")
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)}")
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))
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)
This is the end of the notebook!