Introduction to Recursion

AQA 4.1.1.16 — Recursive techniques

Retrieval: the previous lesson traced exactly how the call stack pushes a new stack frame for every function call, and pops it on return. Recursion puts that mechanism to direct use — a recursive function is really just a function that keeps calling itself, pushing a new stack frame each time.

Key vocabulary

• Recursive function — a function that calls itself.
• Base case — the simplest version of the problem, solved directly without any further recursive call.
• Recursive case — the step where the function calls itself with a smaller version of the problem, moving it closer to the base case.

Understand — why every recursive function needs exactly these two parts

A recursive function without a base case would call itself forever, pushing stack frame after stack frame until Python runs out of room and raises RecursionError — there would never be anything for the calls to return to. A recursive case that doesn't genuinely shrink the problem has the same failure, just less obviously: it might look like it's making progress while never actually reaching the base case. Both parts are required together: the base case gives recursion somewhere to stop, and the recursive case guarantees it actually gets there.

See it — factorial

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

print(factorial(5))   # 120

Trace it — factorial(3), stack frame by stack frame

factorial(3) = 3 * factorial(2)
             = 3 * (2 * factorial(1))
             = 3 * (2 * (1 * factorial(0)))
             = 3 * (2 * (1 * 1))
             = 6

Each call's stack frame stays on the call stack, waiting, until the call beneath it returns a value — exactly the mechanism from the previous lesson, just with the same function appearing in every frame instead of different ones.

Recursion vs iteration

Anything recursion can do, a loop can also do — the choice is about clarity vs overhead. Recursion often expresses naturally-recursive problems (tree traversal, the Fibonacci sequence, recursive search) more clearly than an equivalent loop, at the cost of extra memory for all those stack frames.

Debug it — diagnose, explain, fix, test, justify

def countdown(n):
    print(n)
    return countdown(n - 1)

countdown(5)

This is meant to print 5, 4, 3, 2, 1, Liftoff! and then stop. Instead it keeps counting into negative numbers until it crashes with RecursionError: maximum recursion depth exceeded.

1. Diagnose: does this function have a base case at all?
2. Explain: why does the recursive case alone — even though n - 1 genuinely shrinks each time — never cause the recursion to stop?
3. Fix: add a base case that stops the recursion at the right point and prints "Liftoff!".
4. Test: confirm your fixed version prints exactly 5, 4, 3, 2, 1, Liftoff! and returns normally, with no RecursionError.
5. Justify: explain why "the recursive case shrinks the problem" is necessary but not sufficient on its own — what does this example prove is also required?

(There is no base case at all - every call reaches the recursive case, regardless of how small n gets, so the recursion genuinely never stops on its own; a shrinking recursive case only guarantees progress TOWARD a base case, not that one exists. Adding "if n == 0: print('Liftoff!'); return" before the recursive call fixes it.)

Common mistake

Forgetting the base case, or writing a recursive case that doesn't actually get closer to it — both produce the same symptom (a RecursionError after exhausting the call stack), but for genuinely different reasons, which is exactly why the debug task above asks you to diagnose which is missing before fixing it, not just patch the symptom.

Check your understanding

A recursive function's base case is if n <= 0:, but its recursive case calls itself with n + 1 instead of n - 1. Will this function ever terminate for a positive starting value of n? (No — n + 1 moves away from the base case (n <= 0), not towards it, so for any positive starting value the base case condition is never reached and the function recurses until RecursionError.)

Challenge

Write a recursive function sum_to(n) that returns the sum of all integers from 1 to n, and trace it by hand for sum_to(4), showing every nested call exactly as the factorial trace above does.

Looking ahead: the next lesson (Writing Recursive Functions) moves from tracing and fixing given recursive functions to designing and writing your own from scratch.