Understanding Recursion — A Level Computer Science Complete Guide

Recursion is one of those topics that either clicks immediately or stays confusing for weeks. It appears on almost every A Level Computer Science paper — usually as a 4–6 mark question asking you to trace a recursive function, write one, or explain how the call stack is involved.

This guide gives you a complete understanding of recursion and the exam technique to score full marks on any recursion question.

---

What recursion is

A recursive function is a function that calls itself as part of its own definition. Every recursive function must have two things:

1. A base case — a condition under which the function returns a result without making a recursive call. This stops the recursion.
2. A recursive case — a call to the same function, but with a simpler or smaller version of the problem.

The base case is essential. Without it, the function calls itself indefinitely until the program runs out of stack memory — causing a stack overflow.

---

A simple example — factorial

The factorial of n (written n!) is n × (n-1) × (n-2) × … × 1.

Mathematical definition:

• n! = 1 (when n = 0) ← base case
• n! = n × (n-1)! (when n > 0) ← recursive case

In Python:

def factorial(n):
    if n == 0:          # Base case
        return 1
    return n * factorial(n - 1)  # Recursive case

print(factorial(4))  # Outputs 24

Tracing factorial(4):

factorial(4) = 4 × factorial(3)
factorial(3) = 3 × factorial(2)
factorial(2) = 2 × factorial(1)
factorial(1) = 1 × factorial(0)
factorial(0) = 1          ← base case reached, stack unwinds

factorial(1) = 1 × 1 = 1
factorial(2) = 2 × 1 = 2
factorial(3) = 3 × 2 = 6
factorial(4) = 4 × 6 = 24 ✓

This unwinding is the key visual to understand. The function doesn’t compute the final answer until it reaches the base case — at which point the call stack unwinds, completing each waiting multiplication in reverse order.

---

The call stack

Every time a function is called, a new stack frame is pushed onto the call stack. This frame contains:

• The local variables
• The return address (where to go when the function returns)
• The parameters passed in

When the function returns, its stack frame is popped from the stack.

For factorial(4), the stack builds up like this:

[factorial(0)] ← top of stack (base case)
[factorial(1)]
[factorial(2)]
[factorial(3)]
[factorial(4)] ← bottom of stack (first call)

Then it unwinds from the top, each frame returning its result to the frame below.

Exam point: If the base case is never reached (e.g. you have if n == 0: return 1 but call factorial(-1)), the stack grows indefinitely → stack overflow / infinite recursion.

---

A harder example — Fibonacci

def fib(n):
    if n <= 1:          # Base case
        return n
    return fib(n-1) + fib(n-2)  # Recursive case

print(fib(5))  # 5

Trace of fib(4):

fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1)
fib(2) = fib(1) + fib(0) = 1 + 0 = 1
fib(1) = 1
fib(3) = 1 + 1 = 2
fib(2) = fib(1) + fib(0) = 1    ← calculated AGAIN
fib(4) = 2 + 1 = 3

Notice that fib(2) is calculated twice. For fib(30), the same subproblems are recalculated millions of times. This makes naive recursive Fibonacci exponentially slow.

---

Memoisation — fixing the problem

Memoisation stores the result of each function call so it is not recomputed. This transforms exponential recursive Fibonacci into linear time:

def fib_memo(n, cache={}):
    if n in cache:
        return cache[n]
    if n <= 1:
        return n
    cache[n] = fib_memo(n-1, cache) + fib_memo(n-2, cache)
    return cache[n]

# Or using Python's built-in decorator:
from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

With memoisation, each value is computed exactly once. fib(1000) is instant rather than taking longer than the age of the universe.

Exam point: Memoisation is a key concept in dynamic programming. If asked why naive recursion is inefficient, answer: “overlapping subproblems are recalculated multiple times — memoisation caches results to avoid redundant computation.”

---

Recursion vs iteration

Feature	Recursion	Iteration
Memory	Stack frame per call — risk of overflow	Constant memory
Speed	Slower (function call overhead)	Faster
Code clarity	Often cleaner for tree/graph problems	More explicit
Natural fit	Tree traversal, divide-and-conquer	Counting, accumulation
Risk	Stack overflow if base case missing	Infinite loop if condition wrong

The exam question: “Why would an iterative solution be preferred over a recursive one?”

Answer: “An iterative solution uses constant memory — there is no risk of stack overflow. Each recursive call adds a stack frame, and deep recursion can exhaust the stack. An iterative solution is also generally faster due to the overhead of function calls in recursion.”

---

Tower of Hanoi — the classic recursion example

Move n discs from peg A to peg C, using peg B, without placing a larger disc on a smaller one.

def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"Move disc 1 from {source} to {target}")
        return
    hanoi(n-1, source, auxiliary, target)   # Move n-1 discs to auxiliary
    print(f"Move disc {n} from {source} to {target}")
    hanoi(n-1, auxiliary, target, source)   # Move n-1 discs from auxiliary

hanoi(3, 'A', 'C', 'B')

For 3 discs, this requires 2³ - 1 = 7 moves. For n discs: 2ⁿ - 1 moves. This demonstrates why some problems that are expressible recursively become intractable for large n.

---

Exam technique for recursion questions

“Write a recursive function to…”

1. Identify the base case first — what is the simplest version of the problem?
2. Write the base case with its return value
3. Write the recursive case — call the function with a simpler version (smaller n, shorter string, etc.)
4. Make sure each recursive call moves toward the base case

“Trace this recursive function…”

1. Write out each function call on a separate line
2. Mark when the base case is reached
3. Show the return values unwinding back up the call stack
4. Write the final returned value clearly

“Explain how the call stack is involved in recursion”

• “Each recursive call adds a new stack frame to the call stack. The stack frame stores local variables and the return address. When the base case is reached, each frame is popped in reverse order (LIFO), computing the final result.”

---

Practice

The Algorithm Archives coding course on this site has practical recursion exercises — write real recursive functions to implement data structures and see the result immediately. The A Level revision notes cover recursion in detail for both AQA 7517 and OCR H446.