Recursion

This lesson covers recursion — a fundamental programming technique in which a subroutine calls itself to solve a problem by reducing it to smaller instances of the same problem. Recursion is one of the most heavily examined topics in A-Level Computer Science: you must be able to write recursive subroutines, trace their execution by hand using the call stack, reason about their efficiency, and convert between recursive and iterative forms. It is deeply connected to stacks, tree traversal and divide-and-conquer algorithms.

---

Spec Mapping

This lesson addresses recursive techniques within the Fundamentals of programming and Fundamentals of algorithms sections of the AQA A-Level Computer Science (7517) specification (subject content area 4.1.1, with strong links to 4.3). It covers: the definition of recursion; the necessity of a base case (stopping condition) and a general (recursive) case that converges on it; how recursive calls are managed by the call stack and how this maps onto the stack data structure (4.2); hand-tracing recursive subroutines and showing return values; stack overflow from missing or non-converging base cases; classic recursive algorithms (factorial, Fibonacci, sum, power); the relationship between recursion and iteration and converting between them; and the natural fit of recursion to tree traversal (4.3.2). You are expected to write, trace and evaluate recursive code.

---

What is recursion?

Recursion is a technique in which a subroutine (a function or procedure) calls itself as part of solving a problem. The strategy is to express the solution to a problem in terms of the solution to a smaller version of the same problem, until the problem becomes small enough to answer directly.

Every correct recursive subroutine must have both of the following:

1. A base case (stopping condition) — at least one input for which the subroutine returns a result directly, without calling itself.
2. A general (recursive) case — the subroutine calls itself with arguments that move closer to the base case.

If the base case is missing, or the recursive calls do not converge towards it, the recursion never stops. Each unfinished call consumes memory on the call stack, so the program eventually runs out of stack space and crashes with a stack overflow error. The two requirements are therefore not optional niceties — they are what separates a valid recursive definition from an infinite loop.

Worked example: factorial

The factorial of a non-negative integer $n$n (written $n!$n!) is the product of all integers from 1 to $n$n. It has a natural recursive definition:

$n! = \begin{cases} 1 & \text{if } n = 0 \\ n \times (n-1)! & \text{if } n > 0 \end{cases}$n!={1n×(n−1)!​if n=0if n>0​

The first line is the base case; the second is the general case, which is defined in terms of a smaller factorial.

AQA-style pseudocode

# AQA-style pseudocode
FUNCTION factorial(n: INTEGER) RETURNS INTEGER
    IF n = 0 THEN
        RETURN 1                    // Base case
    ELSE
        RETURN n * factorial(n - 1) // General case (converges on n = 0)
    END IF
END FUNCTION

Python

def factorial(n: int) -> int:
    if n == 0:
        return 1                     # base case
    else:
        return n * factorial(n - 1)  # general case

print(factorial(5))  # Output: 120

---

Tracing recursive calls

Hand-tracing is an examined skill. There are two phases: the winding phase, where calls are made and stacked up (no value can be returned yet because each call is waiting on a smaller one), and the unwinding phase, where the base case returns and the pending multiplications resolve from the deepest call back to the first.

The trace for factorial(4) is shown below. Read downwards for the winding phase and upwards for the returns.

Call made	n	Pending expression	Eventually returns
factorial(4)	4	4 * factorial(3)	24
factorial(3)	3	3 * factorial(2)	6
factorial(2)	2	2 * factorial(1)	2
factorial(1)	1	1 * factorial(0)	1
factorial(0)	0	base case → 1	1

Once factorial(0) returns 1, the suspended calls complete in reverse: factorial(1) returns $1 \times 1 = 1$1×1=1, factorial(2) returns $2 \times 1 = 2$2×1=2, factorial(3) returns $3 \times 2 = 6$3×2=6, and finally factorial(4) returns $4 \times 6 = 24$4×6=24.

Exam Tip: When asked to trace recursion, write the winding phase first (each call and what it is waiting to multiply), reach the base case, then resolve the returns upwards. Showing both phases earns the method marks even if you slip on arithmetic.

---

The call stack

When any subroutine is called, the run-time system pushes a stack frame onto the call stack. Each frame stores that call's parameter values, its local variables, and the return address (where execution resumes once the call finishes). Recursion produces one frame per active call, all present on the stack simultaneously during the winding phase.

The diagram below shows the call stack at its deepest point during factorial(4), the moment the base case is about to return. The most recent call sits at the top; frames are popped (removed) one at a time as each call returns.

flowchart TB
    F0["factorial(0)  — TOP, base case, returns 1"]
    F1["factorial(1)  — waiting on 1 * factorial(0)"]
    F2["factorial(2)  — waiting on 2 * factorial(1)"]
    F3["factorial(3)  — waiting on 3 * factorial(2)"]
    F4["factorial(4)  — BOTTOM, first call, waiting on 4 * factorial(3)"]
    F0 --> F1 --> F2 --> F3 --> F4

This is exactly the stack abstract data type from area 4.2 — last-in, first-out. The last call made (factorial(0)) is the first to complete, and its return value flows back to the call directly beneath it. Understanding that the call stack is a stack is a key synoptic idea.

Stack overflow

Each frame occupies memory. If the base case is never reached — or if the recursion is simply too deep — the stack exhausts its allocated memory and the program terminates with a stack overflow. To protect against runaway recursion, Python imposes a default recursion limit of around 1000 frames; exceeding it raises a RecursionError. A missing or unreachable base case is the most common cause:

def broken(n):
    return n * broken(n - 1)   # no base case → recurses forever → crash

---

Classic recursive algorithms

Fibonacci sequence

$\text{fib}(n) = \begin{cases} 0 & n = 0 \\ 1 & n = 1 \\ \text{fib}(n-1) + \text{fib}(n-2) & n > 1 \end{cases}$fib(n)=⎩⎨⎧​01fib(n−1)+fib(n−2)​n=0n=1n>1​

def fibonacci(n: int) -> int:
    if n <= 0:
        return 0                 # base case
    elif n == 1:
        return 1                 # base case
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)  # two recursive calls

print(fibonacci(7))  # Output: 13

This naive version has two recursive calls, so its call structure is a tree, not a chain. The call tree for fibonacci(4) shows why it is so wasteful — fibonacci(2) is computed twice and fibonacci(1) three times:

flowchart TB
    A["fib(4)"] --> B["fib(3)"]
    A --> C["fib(2)"]
    B --> D["fib(2)"]
    B --> E["fib(1)"]
    D --> F["fib(1)"]
    D --> G["fib(0)"]
    C --> H["fib(1)"]
    C --> I["fib(0)"]

The number of calls grows exponentially, giving a time complexity of $O(2^n)$O(2n). An iterative version (or memoisation, caching previously computed results) reduces this to $O(n)$O(n) — a striking illustration that an elegant recursive definition is not always an efficient algorithm.

Power function

def power(base: float, exp: int) -> float:
    if exp == 0:
        return 1                          # base case
    else:
        return base * power(base, exp - 1) # general case

print(power(2, 10))  # Output: 1024

Sum of a list

def sum_list(lst: list) -> int:
    if len(lst) == 0:
        return 0                           # base case: empty list
    else:
        return lst[0] + sum_list(lst[1:])  # head + sum of the tail

print(sum_list([3, 7, 2, 5]))  # Output: 17

This "head plus the result on the tail" pattern is the standard recursive shape for processing any linear collection, and it generalises directly to traversing a linked list (4.2).

---

Recursion versus iteration

Every recursive algorithm has an equivalent iterative form and vice versa, but each style suits different problems.

Feature	Recursion	Iteration
Mechanism	A subroutine calls itself	A loop (for / while) repeats a block
Memory	One stack frame per active call — risk of stack overflow	Constant extra memory
Readability	Often mirrors the mathematical/recursive definition closely	Often clearer for simple repetition
Performance	Function-call overhead per level; can be slower	Generally faster, no call overhead
Termination risk	Stack overflow if base case is wrong	Infinite loop if condition is wrong
Best suited to	Trees, graphs, divide-and-conquer, naturally recursive structures	Counting, summing, linear passes over arrays

Iterative factorial

def factorial_iterative(n: int) -> int:
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

The iterative version uses a fixed amount of memory regardless of n, whereas the recursive version stacks n frames. For a problem as linear as factorial, iteration is the pragmatic choice; recursion earns its keep when the data itself is recursive, such as a tree.

Exam Tip: You may be asked to convert recursion to iteration or vice versa, and to justify when each is appropriate. The strongest justifications mention memory (call-stack growth) and the shape of the data (recursive structures favour recursion).

---

Recursion and tree traversal

The reason recursion is examined alongside data structures is that tree traversals are most naturally expressed recursively (4.3.2). A binary tree is itself a recursive structure — each node has a left subtree and a right subtree, each of which is a binary tree. An in-order traversal is just: traverse the left subtree, visit the node, traverse the right subtree.

def in_order(node) -> None:
    if node is not None:          # base case: empty subtree → do nothing
        in_order(node.left)       # recurse left
        print(node.value)         # visit
        in_order(node.right)      # recurse right

The base case here is "the subtree is empty"; the recursive calls shrink the problem to the left and right children. The same three-line shape, reordered, gives pre-order and post-order traversals. Trying to write these iteratively requires you to manage an explicit stack by hand — precisely the stack the recursion gives you for free.

---

Tail recursion

A recursive call is in tail position if it is the last action the subroutine performs — there is no pending computation waiting on its result. In factorial, the call is not in tail position because a multiplication (n * ...) still happens after it returns. Rewriting with an accumulator moves the call to the tail:

# NOT tail recursive: multiply happens AFTER the call returns
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

# Tail recursive: nothing is pending after the recursive call
def factorial_tail(n, accumulator=1):
    if n == 0:
        return accumulator
    return factorial_tail(n - 1, accumulator * n)

Some compilers perform tail call optimisation, reusing a single stack frame for tail-recursive calls and so eliminating the stack-overflow risk (effectively turning the recursion into a loop). Languages such as Scheme and Haskell guarantee this; Python deliberately does not, so tail recursion offers no memory saving in Python but remains an important concept.

Exam Tip: Be ready to identify whether a given recursive call is in tail position and to explain that tail call optimisation lets a compiler run such recursion in constant stack space.

---

Recursion in divide-and-conquer: binary search

Recursion is the natural expression of divide-and-conquer, where a problem is split into smaller self-similar subproblems. Binary search is the textbook example: to find a target in a sorted list, look at the middle element; if it matches you are done, otherwise recurse into whichever half could contain the target — discarding the other half entirely.

def binary_search(arr: list, target: int, low: int, high: int) -> int:
    if low > high:
        return -1                       # base case: not found
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid                      # base case: found
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, high)   # search right half
    else:
        return binary_search(arr, target, low, mid - 1)    # search left half

There are two base cases (target found, or the search window collapses to nothing) and two recursive cases (go left, go right). Trace binary_search([2, 5, 8, 12, 16, 23, 38], 23, 0, 6):

Call	low	high	mid	arr[mid]	Decision
1	0	6	3	12	12 < 23 → search right (mid+1..high)
2	4	6	5	23	match → return 5

Each call halves the search space, so the number of calls is at most $\lceil \log_2 n \rceil$⌈log2​n⌉, giving a time complexity of $O(\log n)$O(logn). This logarithmic cost is the reason binary search dramatically outperforms a linear scan on large sorted data — and the recursive formulation makes the "discard half each time" logic transparent.

---

Recurrence relations and the cost of recursion

The running time of a recursive algorithm is naturally described by a recurrence relation: an equation expressing the cost on input size $n$n in terms of the cost on smaller inputs. For binary search, each call does a constant amount of work and then makes one recursive call on half the data:

$T(n) = T\!\left(\frac{n}{2}\right) + O(1)$T(n)=T(2n​)+O(1)

which solves to $T(n) = O(\log n)$T(n)=O(logn). For the naive Fibonacci, each call spawns two calls on nearly the full size:

$T(n) = T(n-1) + T(n-2) + O(1)$T(n)=T(n−1)+T(n−2)+O(1)

which grows like $O(2^n)$O(2n). Contrast a divide-and-conquer sort such as merge sort, which splits into two halves and does linear work to merge:

$T(n) = 2\,T\!\left(\frac{n}{2}\right) + O(n) \;=\; O(n \log n)$T(n)=2T(2n​)+O(n)=O(nlogn)

You are not expected to solve recurrences formally at A-Level, but you are expected to recognise that the shape of the recursion — how many recursive calls, on how much smaller a problem — determines the efficiency. One recursive call on half the data is cheap; two calls on almost the whole data is ruinously expensive.

---

Merge sort: recursion that pays off