5.4 Recursion

Recursion is the process of a function calling itself. It can break a complex problem into smaller versions of the same problem, but it can also create repeated work and a growing call stack.

Two parts of recursion

A recursive function usually needs two parts:

• Base case: stop recursing and return a direct result.
• Recursive case: make the problem smaller and call itself.

Without a base case, the function calls itself forever until the call stack overflows.

def tell_story():
    print("Once upon a time...")
    tell_story()

Factorial

Factorial is a classic first recursion example.

def factorial(n):
    if n == 0 or n == 1:
        return 1
    return n * factorial(n - 1)

print("5! = %d" % factorial(5))

Output:

5! = 120

factorial(5) first calls factorial(4), then factorial(3), until it reaches factorial(1). Only then do the results return upward.

Ackermann's Function

Ackermann's function is a classic recursion example. Unlike factorial, it does not simply subtract 1 from n; it chooses different recursive branches based on both m and n.

def ackermann(m, n):
    if m == 0:
        return n + 1
    if n == 0:
        return ackermann(m - 1, 1)
    return ackermann(m - 1, ackermann(m, n - 1))

print(ackermann(2, 2))

Output:

7

This function is useful for seeing recursion nested inside recursion, but it grows extremely fast. As a beginner, only try very small inputs such as ackermann(2, 2) or ackermann(3, 1).

The cost of recursion

Recursive code can be concise, but every recursive call creates a function call. For large inputs, this can be slow or even overflow the stack.

def fibonacci(n):
    if n == 1 or n == 2:
        return 1
    return fibonacci(n - 2) + fibonacci(n - 1)

print(fibonacci(7))

Output:

13

This version repeats many calculations. For example, both fibonacci(5) and fibonacci(4) eventually compute fibonacci(3).

Tower of Hanoi

Some problems are naturally recursive. Tower of Hanoi can be described as:

1. Move the top n - 1 disks from the source peg to the helper peg. 2. Move the largest disk from the source peg to the destination peg. 3. Move the n - 1 disks from the helper peg to the destination peg.

move = 0

def hanoi(n, src, mid, dst):
    global move

    if n == 1:
        print(src, "->", dst)
        move += 1
    else:
        hanoi(n - 1, src, dst, mid)
        print(src, "->", dst)
        move += 1
        hanoi(n - 1, mid, src, dst)

hanoi(3, "A", "B", "C")
print("Moves: %d" % move)

Output:

A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C
Moves: 7

Each visible move moves only one disk, but the recursive task is "move the top n - 1 disks first, then move the largest disk." Use the lab below to step through the three pegs.

Recursion is not for looking clever. It is useful when a problem has a naturally self-similar structure.