Base case and recursive case

A recursive function solves a problem by calling itself on a smaller version of the same problem. It works when two things are true: the smallest problems are answered directly, and every call makes the problem smaller.

Two parts

Every recursive function has two parts:

• the base case: a problem small enough to answer with no further call;
• the recursive case: the function calls itself on a smaller problem, then uses that answer to build its own.

def total(a):
    if not a:                    # base case: the empty list
        return 0
    return a[0] + total(a[1:])   # recursive case: a shorter list

def total(a):
    if not a:               # base case
        return 0
    return a[0] + total(a[1:])

This version copies the list with a[1:] at each call, which makes the total work grow with n times n, O(n²) (BIGO-8). It is written this way here because it is easy to read. Real code passes an index instead: total(a, i + 1).

Trust the smaller call

When you write the recursive case, do not trace every call in your head. Assume the call on the smaller problem returns the right answer. Then ask only: given that answer, how do I build mine? This is safe because of induction (CORR-3):

• The base case is correct: that is the base step of the proof.
• If the call on a smaller input is correct, the current call is correct: that is the inductive step.

Make sure it gets smaller

“Smaller” must mean that some whole number goes down with every call and cannot go below the base case. For total it is the length of the list. For fact(n) it is n. This is the same idea as proving a loop stops (CORR-2).

Common mistakes:

• No base case, or a base case that some inputs never reach. fact(-1) with a base case of n == 0 never stops.
• A recursive call on the same input. f(n) calling f(n) never shrinks.
• Forgetting to return the recursive answer. The call happens, but its result is thrown away and the function returns None.

Python stops a recursion that is about 1,000 calls deep with RecursionError. That protects you from endless recursion, but it also limits correct recursion on long lists. Lesson 6 shows the fix.

Shrinking by half

A problem that shrinks by one each time needs n calls. A problem that halves each time needs only about log₂ n, the number of times n can be halved before it reaches 1. Raising a number to a power is a good example:

To work out xⁿ (n copies of x multiplied together), first work out x to the power n // 2, half of n rounded down, with one recursive call. Call the answer half. Then:

half = power(x, n // 2)     # one call, not two
if n % 2 == 0:
    return half * half      # an even n: two halves
return half * half * x      # an odd n needs one more x

The base case is n = 0, where the answer is 1. power(x, 1000000) makes about 20 calls instead of a million multiplications. Calling power(x, n // 2) twice instead of storing it in half would undo the saving: the calls would double at each level, back to n in total.

Now try RECR-P1, Power on a clock.