Lab 13: Reference - Recursion Design Patterns

This reference page contains examples of common recursive design patterns in CS111

# ------------------------------------
# Character Patterns
# ------------------------------------
def countDown(n):
    if n <= 0: # Base case
        pass
    else:
        # Act
        print(n)

        # Recurse
        countDown(n-1)

def tower(name):
    if len(name) == 0:  # Base case
        pass
    else:
        # Act
        print(name)

        # Recurse
        tower(name[1:])

def countDownUp(n):
    if n <= 0: # Base case
        pass
    else:
        # Act
        print(n)

        # Recurse
        countDownUp(n-1)

        # Act
        print(n)

# ------------------------------------
# Turtle patterns
# ------------------------------------
from turtle import *

def spiral(sideLen, angle, scaleFactor, minLength):

    if sideLen >= minLength:
    # Implicit base case: no action if sideLen < minLength

        # Act
        fd(sideLen)

        # Setup
        lt(angle)

        # Recurse
        spiral(sideLen*scaleFactor, angle, scaleFactor, minLength)

def spiralBack(sideLen, angle, scaleFactor, minLength):

    # Implicit base case: no action if sideLen < minLength
    if sideLen >= minLength:

        # Act
        fd(sideLen)

        # Setup
        lt(angle)

        # Recurse
        spiralBack(sideLen*scaleFactor, angle, scaleFactor, minLength) # Recurse

        # Invariate
        pu()
        rt(angle)
        bk(sideLen)
        pd()

# ------------------------------------
# Graphic Patterns
# ------------------------------------
from cs1graphics import *

def drawDisc(canvas, x, y, radius, color):
    """ Helper function that adds a circle 
    with given radius at (x, y) on the given 
    canvas with given color
    """
    c = Circle(radius, Point(x,y))
    c.setFillColor(color)
    canvas.add(c)

def drawTarget(canvas, x, y, radius, thickness, color1, color2):
    if radius < thickness:  # Base case
        pass
    else:

        # Act
        drawDisc(canvas, x, y, radius, color1)

        # Recurse
        drawTarget(canvas, x, y, radius-thickness, thickness, color2,color1)  # Recurse

#paper = Canvas(650, 600, 'darkolivegreen', 'Bullseye')
#drawTarget(paper, 225, 225, 200, 10, 'purple', 'orange')
#paper.close()

Table of Contents