Recursion: Base Cases, the Call Stack & vs Iteration (OCR A-Level CS 2.2.1)
OCR A-Level CS 2.2.1: how recursion works — base case, general case and the call stack — how to trace a recursive function, and how it compares to iteration.
Free Recursion revision resources (OCR A-Level Computer Science, 2.2.1)
We’ve made exam-style practice for this exact topic, free to download: Recursion question sheet, mark scheme and cheat sheet. Grab them, have a go, then read the full guide below.
A recursive function calls itself. It sounds like a trick, but it's a clean way to solve problems that break into smaller copies of themselves. Spec point 2.2.1(b) covers how recursion works, how to trace it, and how it compares to an iterative (loop-based) approach — and Paper 2 nearly always includes a "trace this recursive algorithm" question worth several marks. Get the trace technique right and these are reliable marks.
The two ingredients: base case and general case
Every correct recursive function needs two parts:
The base case — the simplest version of the problem, which is solved directly without recursing. It's the stop condition.
The general (recursive) case — solves the problem in terms of a smaller version of itself, moving towards the base case.
The classic example is factorial. By definition n! = n × (n−1)!, and 1! = 1. In OCR pseudocode:
Each call makes n smaller, so it always heads toward the base case of n = 1. Without a base case (or if the general case didn't shrink the problem), it would recurse forever.
The call stack: winding down and unwinding up
Recursion relies on the call stack. Each time the function calls itself, the current call is paused and its details (the value of n, where to return to) are pushed onto the stack. This continues until the base case is reached — then the calls return in reverse order, each popped off the stack, passing its result back up.
Tracing factorial(4) makes it concrete — it winds down to the base case, then unwinds up, multiplying as it returns:
Call | What it returns |
|---|---|
factorial(4) | 4 × factorial(3) = 4 × 6 = 24 |
factorial(3) | 3 × factorial(2) = 3 × 2 = 6 |
factorial(2) | 2 × factorial(1) = 2 × 1 = 2 |
factorial(1) | base case → 1 |
Read the table bottom-up: 1, then 2, then 6, then 24. The final answer is 24. That bottom-up unwinding is the heart of every recursion trace.
Recursion vs iteration
The same problems can usually be solved with a loop (iteration) instead. OCR wants you to compare them:
Recursion is often shorter and more elegant for naturally recursive problems (factorials, tree traversals, divide-and-conquer like merge sort). But every call uses stack memory, so deep recursion can cause a stack overflow, and the call overhead can make it slower.
Iteration uses a fixed amount of memory (no growing stack) and is usually faster, but the code can be clumsier for problems that are naturally recursive.
Rule of thumb: naturally recursive structure → recursion is clearer; performance or memory critical, or deep nesting → iteration is safer. Any recursive function can be rewritten iteratively (often using your own stack), and vice versa.
Worked example: trace sumTo(3)
Calling sumTo(3):
sumTo(3)= 3 +sumTo(2)sumTo(2)= 2 +sumTo(1)sumTo(1)= 1 +sumTo(0)sumTo(0)= 0 (base case)
Unwinding: 0 → 1 → 3 → 6. So sumTo(3) returns 6 (that's 3 + 2 + 1). Same shape as factorial — find the base case, wind down, then add/multiply back up.
Common exam mistakes
No base case (or one that's never reached). Without a reachable stop condition, recursion runs forever → stack overflow.
The general case doesn't shrink the problem. Each call must move towards the base case.
Reading the trace top-down. The values are resolved bottom-up, as the calls return.
Forgetting the stack. Each call is pushed; results are popped and returned in reverse order.
Saying recursion is always better. It's elegant but uses stack memory and can be slower than a loop.
Quick recap
A recursive function calls itself; it needs a base case (stop condition) and a general case (a smaller sub-problem).
Calls are pushed onto the call stack winding down to the base case, then popped and returned, unwinding back up.
Trace bottom-up: solve the base case, then work back up through the returns.
Recursion = elegant for recursive problems but uses stack memory (risk of stack overflow) and can be slower.
Iteration = fixed memory, usually faster, but clumsier for naturally recursive problems.
Frequently asked questions
What is recursion? Recursion is a technique where a function calls itself to solve a problem by breaking it into smaller versions of the same problem. A recursive function has a base case that is solved directly and a general case that calls the function on a smaller input, moving towards the base case.
What is a base case in recursion? A base case is the simplest version of the problem, which is solved directly without any further recursive calls. It acts as the stop condition; without a reachable base case the function would call itself forever and cause a stack overflow.
How does the call stack work in recursion? Each time a recursive function calls itself, the current call is paused and pushed onto the call stack, storing its data and return point. When the base case is reached, the calls return in reverse order, each popped off the stack, passing its result back up to the call that made it.
How do you trace a recursive function? Write down each call as it winds down to the base case, then resolve the values bottom-up as the calls return. For example, factorial(4) calls factorial(3), factorial(2) and factorial(1); once factorial(1) returns 1, the results multiply back up to 2, 6 and finally 24.
What is the difference between recursion and iteration? Recursion solves a problem by a function calling itself and uses the call stack, which makes it elegant for naturally recursive problems but risks a stack overflow and can be slower. Iteration uses a loop and a fixed amount of memory, so it is usually faster and safer for deep repetition, though the code can be clumsier for recursive problems.
What is a stack overflow in recursion? A stack overflow happens when recursion goes too deep and the call stack runs out of memory, because each unfinished recursive call takes up stack space. It is usually caused by a missing or unreachable base case, or by recursing too many times for the available stack.
