CAIE 9618 · Paper 2 · Topic 2.4.4

Recursion

Base Case · Recursive Calls · Call Stack · Worked Trace · vs Iteration

CSZone Cambridge International AS & A Level Computer Science 9618

What is Recursion?

A Function That Calls Itself

Recursion is when a function (or procedure) calls itself as part of its own definition. Every recursive solution must have two components: a base case that stops the recursion, and a recursive case that moves towards the base case.

BASE CASE

The condition that terminates the recursion. When reached, the function returns a value directly without calling itself again. Without a base case, recursion is infinite.

RECURSIVE CASE

The part where the function calls itself with a simpler (smaller) version of the problem, moving one step closer to the base case with each call.

Worked Example — Factorial

Factorial(n) = n × (n−1)!

CAIE PSEUDOCODE

FUNCTION Factorial(n : INTEGER) : INTEGER
IF n = 0 THEN
RETURN 1 // base case
ELSE
RETURN n * Factorial(n - 1)
ENDIF
ENDFUNCTION

TRACE: 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!
// Unwinding:
= 1×1=1, 2×1=2, 3×2=6, 4×6=24

The recursion winds (builds up calls) until the base case, then unwinds (returns values back through each frame) to produce the final answer.

The Call Stack

How Recursion Uses Memory

Each recursive call creates a new stack frame on the call stack, storing the function's local variables, parameters, and return address.

WHAT EACH FRAME STORES

Local variables for that call
Parameter values passed in
Return address (where to go back to)
Each frame uses memory — deep recursion risks stack overflow

WINDING (growing)

Stack grows as each call is made: Factorial(4) → Factorial(3) → … → Factorial(0)

UNWINDING (returning)

Base case returns, frames pop off: Factorial(0) returns 1 → Factorial(1) returns 1 → … → Factorial(4) returns 24

Recursion vs Iteration

Comparing the Two Approaches

ASPECT	RECURSION	ITERATION
Memory	O(n) — call stack grows	O(1) — fixed variables
Speed	Slower (function call overhead)	Faster (no overhead)
Code clarity	Often cleaner/shorter	Can be more complex
Risk	Stack overflow if deep	No stack overflow risk
Best for	Trees, fractals, divide & conquer	Simple loops, counters

Exam Practice

Cambridge-style questions

Question 1

The following recursive function is defined: Mystery(n) returns n + Mystery(n-1) with base case Mystery(0) = 0. Trace the execution of Mystery(4), showing the call stack and the value returned.

4 marks

Mystery(4) → 4 + Mystery(3) 1
Mystery(3) → 3 + Mystery(2)
Mystery(2) → 2 + Mystery(1)
Mystery(1) → 1 + Mystery(0) 1
Mystery(0) → 0 (base case) 1
Unwinding: 0, 1+0=1, 2+1=3, 3+3=6, 4+6=10 1

Exam Practice

Cambridge-style questions

Question 2

Explain what happens if a recursive function is called without a correctly defined base case. Your answer should refer to the call stack. [3 marks]

3 marks

Without a valid base case, the function calls itself indefinitely. 1
Each call adds a new stack frame to the call stack. 1
The call stack eventually runs out of space, causing a stack overflow error, which crashes the program. 1

Common Mistakes

Don't lose easy marks

1

Missing the base case in pseudocode answers. Every recursive function must have a base case. Examiners will deduct marks if the termination condition is absent or unreachable.

2

Not showing the unwinding phase in a trace. A trace must show both: the winding (calls building up) AND the unwinding (return values propagating back). Write out each step explicitly.

3

Confusing stack overflow with stack underflow. Stack overflow is caused by too many recursive calls filling the call stack. Don't say "the program loops forever" — the OS terminates it with a stack overflow error.

Topic Summary — 2.4.4

What You Need to Know

RECURSION ESSENTIALS

Base case — terminates recursion
Recursive case — calls self with smaller problem
Each call creates a stack frame

CALL STACK

Grows on each call (winding)
Shrinks when base case returns (unwinding)
Stack overflow if too deep / no base case

vs ITERATION

Recursion: elegant but O(n) memory, overhead
Iteration: faster, O(1) memory, no overflow risk
Use recursion for inherently recursive problems (trees, fractals)

CSZone

Next Topic

2.4.5

Big-O Notation

Time Complexity · O(1) · O(n) · O(log n) · O(n²)

Head to CSZone.co.uk for the complete worksheet, quiz, and interactive tools