Recursion

Recursion and the call stack

A recursive subprogram is one that calls itself. It solves a problem by solving a smaller version of the same problem, and it needs two things:

• a base case, a version of the problem small enough to answer directly, with no further call
• a recursive case, which does a little work and calls itself with an argument that is closer to the base case

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

print(factorial(5))                # 120

factorial(4) cannot give its answer until factorial(3) has, and that waits on factorial(2). The answer is built as the calls unwind:

factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * (3 * (2 * 1))
= 24

The call stack

Every call needs somewhere to keep its own parameters, local variables and the place to return to. The computer keeps these in a stack frame, and the frames are held on the call stack. A call pushes a frame. A return pops one.

This version prints each call and each return, indented by how deep it is, so you can watch the stack grow and shrink:

def factorial(n, depth=0):
    print("  " * depth + "call factorial(" + str(n) + ")")
    if n <= 1:
        print("  " * depth + "base case, return 1")
        return 1
    result = n * factorial(n - 1, depth + 1)
    print("  " * depth + "return " + str(result))
    return result

factorial(4)

Without a base case

If the recursion never reaches a base case, frames pile up until the stack is full. Python stops it at about a thousand frames and raises a RecursionError. Other languages call the same event a stack overflow.

# raises: RecursionError
def runaway(n):
    return runaway(n + 1)

runaway(0)

More small examples

The same pattern, a base case and a smaller problem, solves many things. In each, find the base case first.

def sum_list(items):
    if items == []:
        return 0
    return items[0] + sum_list(items[1:])     # the head, plus the sum of the tail

def reverse(text):
    if len(text) <= 1:
        return text
    return reverse(text[1:]) + text[0]

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

print(sum_list([4, 8, 15, 16]))      # 43
print(reverse("recursion"))          # noisrucer
print(gcd(48, 18))                   # 6

sum_list splits a list into its head (items[0]) and its tail (items[1:]). You will meet that pair again in functional programming.

The cost of recursion, and how to cut it

Recursion is elegant and it is not free. The call stack takes memory, and the naive version of some recursive functions repeats the same work again and again.

The Fibonacci trap

Each Fibonacci number is the sum of the two before it, so the definition is recursive. The code writes itself:

calls = 0

def fib(n):
    global calls
    calls += 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(20), calls)       # 6765 21891

Twenty one thousand calls to get an answer that needs twenty additions. fib(5) calls fib(3) and fib(4), and fib(4) calls fib(3) again. The tree of calls roughly doubles with each step, so the work grows as 2 to the power of n.

Memoisation

Memoisation stores each result the first time it is worked out, so a repeat call is answered from the store. Python's functools.lru_cache does it with one line.

from functools import lru_cache

calls = 0

@lru_cache(maxsize=None)
def fib(n):
    global calls
    calls += 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(80), calls)       # 23416728348467685 81

fib(80) would take longer than a human lifetime without the cache. With it, the function body runs just 81 times, once for each value from 0 to 80. This trades memory for time.

Recursion or iteration

Anything recursion can do, a loop can do, and the reverse. Choosing between them is a judgement.

def factorial_loop(n):
    result = 1
    for i in range(2, n + 1):
        result = result * i
    return result

print(factorial_loop(5))     # 120

In Python the limit matters in practice, because the language does not optimise a call that is the last thing a function does:

# raises: RecursionError
def depth(n):
    if n == 0:
        return 0
    return 1 + depth(n - 1)

print(depth(900))
print(depth(5000))

Problems that recurse: Hanoi, nesting and backtracking

Tower of Hanoi

Three pegs and a stack of disks, largest at the bottom. Move the whole stack to another peg, one disk at a time, never putting a bigger disk on a smaller one. The recursive idea: to move n disks, move the top n - 1 out of the way, move the biggest, then move the n - 1 back on top.

def hanoi(n, source, target, spare):
    if n == 0:
        return 0
    moves = hanoi(n - 1, source, spare, target)
    print("move disk", n, "from", source, "to", target)
    moves = moves + 1
    moves = moves + hanoi(n - 1, spare, target, source)
    return moves

total = hanoi(3, "A", "C", "B")
print(total, "moves")       # 7 moves

Each extra disk doubles the number of moves and adds one: n disks need 2 to the n minus 1. Sixty four disks, the legend's number, needs 18 quintillion moves.

Nested data

A loop cannot easily handle lists inside lists inside lists, because you do not know how deep it goes. Recursion does not need to.

def flatten(items):
    result = []
    for item in items:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result

print(flatten([1, [2, [3, 4]], [5], 6]))     # [1, 2, 3, 4, 5, 6]

Backtracking

Backtracking tries a choice, carries on, and if it reaches a dead end it undoes the choice and tries another. It is a recursive search, and the path.pop() below is the undo.

maze = [
    "S.#.....",
    ".##.###.",
    "....#...",
    ".####.#.",
    "......#E",
]

def solve(row, col, path, seen):
    if not (0 <= row < len(maze) and 0 <= col < len(maze[0])):
        return False
    if maze[row][col] == "#" or (row, col) in seen:
        return False
    seen.add((row, col))
    path.append((row, col))
    if maze[row][col] == "E":
        return True
    for step_row, step_col in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
        if solve(row + step_row, col + step_col, path, seen):
            return True
    path.pop()                  # dead end: undo this square and back up
    return False

path = []
seen = set()
if solve(0, 0, path, seen):
    grid = [list(line) for line in maze]
    for row, col in path[1:-1]:
        grid[row][col] = "*"
    for line in grid:
        print("".join(line))
    print("path of", len(path), "squares; tried", len(seen), "to find it")

The solver tries right, then down, then left, then up. At the start it goes right, finds a wall, and backs up. The gap between the two numbers printed is the squares it tried and had to abandon.

Key terms you must be able to define

Recursion

A technique in which a subprogram solves a problem by calling itself with a smaller version of the same problem.

Base case

The case in a recursive subprogram that is answered directly, without another recursive call, and which stops the recursion.

Recursive case

The case in a recursive subprogram that makes a call to itself, with an argument closer to the base case.

Call stack

The area of memory that holds a stack frame for each active call, with its parameters, locals and return address.

Stack frame

The block of the call stack belonging to one call of a subprogram.

Stack overflow

An error when the call stack runs out of space, usually from recursion that never reaches its base case.

Memoisation

Storing the result of each call so that a repeated call with the same argument is answered without recalculating.

Backtracking

Trying a choice, and undoing it to try another if it leads to a dead end.

Divide and conquer

Splitting a problem into smaller copies of itself, solving each and combining the results.

Flashcards

Say the definition out loud before you flip the card. Retrieving it from memory is what builds recall, reading it again is not.

Reach the top grade on this topic

Recursion is examined as tracing, writing and judging. The top marks come from precision about the stack.

• Identify the base case and the recursive case separately, and say that each call moves towards the base case
• When tracing, write the calls going down and then the values returning back up
• Explain a stack overflow as the stack frames using up the available memory
• In a comparison, give a cost and a benefit of each: memory and speed against clarity
• Recognise when memoisation applies: the same arguments are being recalculated

Mistakes that cost marks here

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

print(mystery(4))

def power(base, exponent):
    if exponent == 0:
        return 1
    return base * power(base, exponent - 1)

print(power(2, 10))