Acknowledgment. This notebook has been adapted from Wellesley CS111 course materials: (http://cs111.wellesley.edu/spring19).
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 < 1:
return 0
else:
return n + sumUp(n-1)
sumUp(5)
sumUp(10)
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 < 1:
return 0
else:
subResult = sumUp(n-1) # Result returned by recursive call
result = n + subResult # Result for whole call
return result
sumUp(4)
Write a recursive function that determines whether a given string is a palindrome or not.
def palindrome(s):
"""Returns True if string s is a
palindrome."""
if len(s) == 0 or len(s) == 1:
return True
else:
subresult = palindrome(s[1:-1])
return s[0].lower() == s[-1].lower() and subresult
palindrome('Ana')
palindrome('Hannah')
palindrome('williams')
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. 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:
def palindromeDebug(s):
"""Returns True if string s is a
palindrome."""
print("Entering palindrome('{}')".format(s))
if len(s) == 0 or len(s) == 1:
print('Reached base case. Returning True')
return True
else:
subresult = palindromeDebug(s[1:-1])
result = s[0].lower() == s[-1].lower() and subresult
print("Returning {} from palindrome('{}')".format(result, s))
return result
palindromeDebug('shannahz')
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"""
if n == 0:
return 1
else:
return n * factorial(n-1)
factorial(5)
factorial(7)
1 * 2 * 3 * 4 * 5
120 * 6 * 7
We'll learn about a new graphics library today, Turtle Graphics.
We will write programs that control the turtle's movements. The turtle leaves a trail behind.
from turtle import *
#setup(400,400, 0, 0) # open the Turtle graphics window
fd(100) # move turtle forward 100 pixels
lt(90) # change direction by 90 degrees left
fd(100) # move forward 100 pixels
pensize(5) # change pen size
pencolor('red') # change pen color
lt(90)
fd(100)
# completing the square
lt(90)
fd(100)
# use clear() to erase the canvas
clear()
Notice that the turtle's properties (pen size and color haven't changed). If in addition to clearing
the drawing we want to return the turtle in its original state, use reset().
reset()
reset()
pensize(5)
speed(1)
fd(100)
lt(60)
pencolor('red')
fd(150)
rt(15)
pencolor('blue')
bk(100)
pd()
pensize(5)
bk(250)
pensize(3)
home()
exitonclick() # click on the canvas to close the window
Oftentimes, it is helpful to control the speed with which the turtle moves.
speed(). Above we have assigned the speed to the slowest setting (i.e., 1). The fastest setting is 10. polygon¶Loops can be used in conjunction with turtles to make interesting designs.
Let's build together the function polygon, which will produce different shapes as shown in the slides.
reset()
def polygon(numSides, sideLength):
'''Draws a polygon with the specified number
of sides, each with the specified length.
'''
for side in range(numSides):
fd(sideLength)
lt(360/numSides)
# Draw a triangle, allow user to click on canvas to close window
# 0,0 sets the position of the canvas at the top-left corner
reset()
pensize(3)
polygon(3, 200)
# Draw a square, click on canvas to close window
# setup(400, 400, 0, 0)
reset()
pensize(5)
polygon(4, 200)
# Draw a pentagon, click on canvas to close window
reset()
pensize(5)
polygon(5, 75)
# Draw an approximate circle, click on canvas to close window
reset()
pensize(5)
polygon(100, 7)
polyflow¶In addition to the simple shapes we saw above, with loops we can create more interesting shapes too, such as geometric flowers. We will use the function polygon to write polyFlow.
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.
'''
for petal in range(numPetals):
polygon(petalSides, petalLen)
rt(360.0/numPetals)
# Example 1: square petals
reset()
pensize(5)
speed(5)
polyFlow(7, 4, 80)
# Example 2: pentagon petals
reset()
pensize(2)
speed(5)
polyFlow(10, 5, 75)
# Example 3: hexagon petals
reset()
pensize(2)
speed(5)
polyFlow(11, 6, 60)
Let's try to write 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:
pass
else:
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 setupTurtle(sideLen):
"""Helper function to prepare the window for drawing and
then calling the spiral function.
"""
reset()
pensize(2)
padding = 100
width = sideLen + padding
height = sideLen + padding
pu()
goto(-height/2+padding/2, -width/2+padding/2)
pd()
reset()
speed(8)
setupTurtle(625)
spiral(625, 90, 0.7, 100)
setupTurtle(700)
spiral(700, 90, 0.9, 10)
setupTurtle(700)
spiral(200, 72, 0.97, 10)
reset()
spiral(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.
The following function is 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.
'''
if sideLen < minLength:
pass
else:
fd(sideLen)
lt(angle)
spiralBack(sideLen*scaleFactor,
angle, scaleFactor, minLength)
rt(angle)
bk(sideLen)
reset()
setupTurtle(500)
pensize(2)
spiralBack(200, 95, 0.93, 10)
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, minLen):
"""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 < minLen:
return 0
else:
fd(sideLen); lt(angle)
subLen = spiralLength(sideLen*scaleFactor,
angle, scaleFactor, minLen)
rt(angle); bk(sideLen)
return sideLen + subLen
resetTurtle()
totalLen = spiralLength(100, 90, 0.5, 5)
print("The total length of the spiral is", totalLen)
resetTurtle()
totalLen = spiralLength(200, 95, 0.93, 10)
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 spiralSideCount(sideLen, angle, scaleFactor, minLen):
"""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 < minLen:
return 0
else:
fd(sideLen); lt(angle)
subCount = spiralSideCount(sideLen*scaleFactor,
angle, scaleFactor, minLen)
rt(angle); bk(sideLen)
return 1 + subCount # Your code here
resetTurtle()
totalCount = spiralSideCount(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:
from turtle import *
def spiralTuple(sideLen, angle, scaleFactor, minLen):
"""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.
"""
if sideLen < minLen:
return (0, 0)
else:
fd(sideLen); lt(angle)
subCount, subLen = spiralTuple(sideLen*scaleFactor,
angle, scaleFactor, minLen)
rt(angle); bk(sideLen)
return 1 + subCount, sideLen + subLen # Your code here
resetTurtle()
spiralTuple(512, 90, 0.5, 5)