Recursion

Base case and general case, winding and unwinding, and a spiral the robot draws by calling itself.

A2.2Recursion and computational thinkingA level25 min

At GCSE, merge sort (F5.9) sorted each half of a list "the same way", with a function that called itself. That idea is recursion: a subroutine that solves a problem by calling itself on a smaller version of the same problem. This lesson is about how to write recursion correctly, and how the call stack from the last lesson makes it work.

Base case and general case

Every correct recursive subroutine has two parts:

• a base case: a version of the problem small enough to answer directly, with no further call. This is what stops the recursion.
• a general case (or recursive case): the subroutine calls itself with a smaller problem, and uses the answer to build its own.

Each recursive call must move closer to the base case. If it does not, or if there is no base case, the calls never end.

The factorial of n, written n!, is 1 × 2 × ... × n, with 0! = 1. It has a natural recursive definition: 0! = 1, and n! = n × (n − 1)! for n > 0.

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

for n in range(6):
    print(n, factorial(n))

Run this in the simulator

Winding and unwinding

A recursive call does not finish until the call it made has finished. So the calls happen in two phases:

• winding: each call makes the next, smaller one, pushing a frame each time, until the base case is reached;
• unwinding: the base case returns, then each waiting call gets its answer, finishes its own work and returns, popping frames in reverse order.

Printing on the way in and on the way out shows both phases. The indent is the depth of the call stack:

def sum_to(n, depth=0):
    pad = "    " * depth
    print(pad + "sum_to(" + str(n) + ") called")
    if n == 0:
        answer = 0
    else:
        answer = n + sum_to(n - 1, depth + 1)
    print(pad + "sum_to(" + str(n) + ") returns " + str(answer))
    return answer

sum_to(3)

Run this in the simulator

For factorial(4) the stack at its deepest holds five frames, one for each value of n from 4 down to 0. Each frame has its own n: that is what lets every call remember which number to multiply by when the answer comes back.

What goes wrong

Two mistakes cause most broken recursion:

1. No base case, or one that is never reached. factorial(-1) calls factorial(-2), and so on for ever, because counting down from −1 never hits 0. Python stops it with a RecursionError; a language without that guard overflows the stack.
2. The general case does not use the returned value. Writing factorial(n - 1) on its own line throws the answer away. The call still happens, but nothing is built from it.

A safer base case covers every value that should stop, for example if n <= 0, as long as that is correct for the problem.

Recursion on the robot

A square spiral is self-similar: a spiral is one side, a turn, and then a smaller spiral. That is a recursive definition, so it becomes a recursive procedure. A procedure can recurse just as a function can; it simply returns no value.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def countdown(n):
    if n == 0:
        tone(880, 0.4)                 # base case: the final, high beep
        print("go")
        return
    print(n)
    tone(440, 0.2)
    countdown(n - 1)

countdown(3)
forward(50, distance=15)

Run this in the simulator

Task: down and back up

Write a recursive procedure echo(n), where n is a whole number from 0 upwards:

• if n is 0 (the base case), print base and play tone(200, 0.2);
• otherwise print down <n> and play tone(200 + 100 * n, 0.2), then call echo(n - 1), then print up <n> and play tone(200 + 100 * n, 0.2) again.

Call echo(3). The output must be down 3, down 2, down 1, base, up 1, up 2, up 3, one per line, and you will hear the notes fall and rise again. Use no loops.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def echo(n):
    print("down", n)

echo(3)

Task: a recursive spiral

Write a recursive procedure spiral(side), where side is a length in cm:

• if side is less than 10 (the base case), print centre and stop;
• otherwise print side <side>, drive forward side cm, turn right 90 degrees, and call spiral with a side 10 cm shorter.

Call spiral(60). The output is side 60, side 50, down to side 10, then centre. Use no loops.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def spiral(side):
    forward(60, distance=side)
    turn_right(30, angle=90)

spiral(60)

Challenges

1. Trace sum_to(4) on paper as a table like the factorial one. How many frames are on the stack at its deepest?
2. Write a recursive power(base, exp) for whole-number exp of 0 or more. What is its base case?
3. Move the print in spiral to after the recursive call. Predict the output before you run it.