Recursion: The Standard Problems

The syllabus names five recursion problems. Each one follows the same recipe from the previous topic: find the base case, find the smaller version of the same problem.

1. Factorial

$n! = n \times (n-1)!$, with $0! = 1$.

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

2. Sum of digits

Already met: last digit plus the digits of the rest.

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

3. Adding two positive integers

Looks artificial, and that is the point — it shows recursion working on something with no obvious "smaller list".

Add one to the first, take one from the second, until the second is 0:

def add(a, b):
    if b == 0:
        return a
    return add(a + 1, b - 1)

add(3, 4) → add(4, 3) → add(5, 2) → add(6, 1) → add(7, 0) → 7.

Note the depth is b, so add(1, 100000) will overflow the stack. It demonstrates the idea; it is not how you would add two numbers.

4. Greatest common divisor

Euclid's algorithm, and one of the genuinely elegant uses of recursion:

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

gcd(48, 18):

gcd(48, 18) -> gcd(18, 48 % 18 = 12)
gcd(18, 12) -> gcd(12, 18 % 12 = 6)
gcd(12, 6)  -> gcd(6,  12 % 6  = 0)
gcd(6, 0)   -> 6                        base case

Answer 6. Four calls for numbers in the forties — the remainder shrinks extremely quickly, which is why Euclid's method is still used.

5. Fibonacci

$F(n) = F(n-1) + F(n-2)$, with $F(0) = 0$ and $F(1) = 1$.

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

Two recursive calls, and that changes everything.

Why naive Fibonacci is slow

Trace fib(5):

                    fib(5)
              /              \
          fib(4)            fib(3)
         /     \            /    \
     fib(3)   fib(2)    fib(2)  fib(1)
     /   \     /   \     /   \
 fib(2) fib(1) ...      ...

fib(3) is computed twice. fib(2) three times. fib(1) five times. The work doubles with each increase in n, so fib(30) makes over 2.6 million calls — for a number you could compute by hand in a minute.

The cause is overlapping sub-problems: the same values are recomputed from scratch again and again. Remembering results fixes it:

def fib_fast(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib_fast(n - 1, memo) + fib_fast(n - 2, memo)
    return memo[n]

Or with a simple loop, which needs no stack at all:

def fib_loop(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

This is exactly the recursion-versus-dynamic-programming comparison the syllabus sets up for Module 4 — Fibonacci is the example it uses.

Choosing recursion

Rule of thumb: one recursive call per level is usually fine. Two or more, on overlapping sub-problems, means you should be memoising or iterating.