1.7 Recursion

Big ideas

• A recursive function calls itself on a smaller version of the problem. It needs a base case that answers directly and a recursive case that shrinks the input toward the base case.
• Classic shapes: factorial(n) = n * factorial(n - 1) with factorial(0) = 1; sum of a list = first item + sum of the rest; countdown; digit sum; powers.
• Each call gets its own local variables and waits on the call stack until the deeper call returns. Too deep (no base case) gives RecursionError.
• Turtle recursion draws trees, spirals and snowflakes: draw one piece, then call yourself with a shorter length until it is too small.
• Anything recursive can be written with a loop; recursion is chosen when the problem is naturally self-similar.

Code you should know

def factorial(n):
    if n == 0:          # base case
        return 1
    return n * factorial(n - 1)

def digit_sum(n):
    if n < 10:
        return n
    return n % 10 + digit_sum(n // 10)

print(factorial(5), digit_sum(4913))

120 17

def countdown(n):
    if n == 0:
        print("Liftoff!")
        return
    print(n)
    countdown(n - 1)
    print("back from", n)

countdown(3)

3
2
1
Liftoff!
back from 1
back from 2
back from 3

import turtle

def branch(t, length):
    if length < 10:
        return
    t.forward(length)
    t.left(30)
    branch(t, length * 0.7)
    t.right(60)
    branch(t, length * 0.7)
    t.left(30)
    t.backward(length)

t = turtle.Turtle()
t.left(90)
t.penup(); t.goto(0, -120); t.pendown()
t.color("darkgreen")
branch(t, 90)
t.hideturtle()

A branching tree.

Worked example

def mystery(n):
    if n <= 1:
        return 1
    return mystery(n - 1) + mystery(n - 2)

Common mistakes

• A base case that is never reached (for example shrinking by 2 from an odd number down past 0).
• Forgetting to return the recursive call, so the answer is lost and the function returns None.
• Not undoing turtle moves after a recursive branch, so the next branch starts in the wrong place.