Cambridge 9618 · International A Level Computer Science · ~16 min read
Notes
Video
Slides
Quiz
Worksheet
What is Recursion?
A recursive routine is a subroutine (function or procedure) that calls itself during its execution. Each call works on a smaller version of the original problem until a simple case is reached that can be solved directly.
Every recursive routine must have exactly two parts:
Base case — the terminating condition; a simple case that can be solved directly without a further recursive call
Recursive case — calls itself with a modified parameter that moves closer to the base case
Without a base case, recursion is infinite — the function calls itself forever, eventually causing a stack overflow because the call stack fills up with unresolved stack frames.
Factorial — Recursive Example
Factorial is defined as: n! = n × (n−1) × (n−2) × ... × 1, and 0! = 1.
FUNCTION Factorial(n : INTEGER) RETURNS INTEGER IF n = 0THEN// base case RETURN1 ELSE// recursive case RETURN n * Factorial(n - 1) ENDIF ENDFUNCTION
Trace — Factorial(4)
Winding down (recursive calls):
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)
Unwinding (returning values):
Factorial(1)returns1 × 1 = 1
Factorial(2)returns2 × 1 = 2
Factorial(3)returns3 × 2 = 6
Factorial(4)returns4 × 6 = 24
The Call Stack
When a recursive function is called, the computer uses a call stack to track each incomplete call. Each call pushes a new stack frame (activation record) containing the local variables and the return address.
Frame 1 (first call, outermost)
Factorial(4) — waiting for Factorial(3) to return
Frame 2
Factorial(3) — waiting for Factorial(2) to return
Frame 3
Factorial(2) — waiting for Factorial(1) to return
Frame 4
Factorial(1) — waiting for Factorial(0) to return
Frame 5 (top of stack — base case)
Factorial(0) → returns 1 immediately
After the base case returns, frames are popped off the stack in reverse order (LIFO), each returning a value to the frame below.
Fibonacci — Second Recursive Example
FUNCTION Fib(n : INTEGER) RETURNS INTEGER IF n <= 1THEN// base case: Fib(0)=0, Fib(1)=1 RETURN n ELSE RETURN Fib(n - 1) + Fib(n - 2) ENDIF ENDFUNCTION
Fibonacci has two recursive calls per invocation, making it far less efficient than factorial (it recomputes the same values many times). Fib(n) has O(2ⁿ) time complexity — extremely slow for large n.
Recursive vs Iterative
Feature
Recursive
Iterative
Code clarity
Often shorter and closer to the mathematical definition
May be longer but easier to trace step-by-step
Memory
Uses call stack — each frame uses memory; risk of stack overflow
Uses a fixed amount of memory (loop variables only)
Speed
Function call overhead for each level
Generally faster — no call stack overhead
Base case
Essential — missing it causes infinite recursion / stack overflow
Loop condition prevents infinite loop
Best for
Problems naturally defined recursively: trees, fractals, divide-and-conquer
Simpler repetitive tasks where performance matters
Iterative Factorial — for Comparison
FUNCTION FactorialIter(n : INTEGER) RETURNS INTEGER DECLARE result, i : INTEGER
result ← 1 FOR i ← 1TO n
result ← result * i NEXT i RETURN result ENDFUNCTION
Both produce the same result. The iterative version uses O(1) memory; the recursive version uses O(n) stack frames.
Cambridge exam — tracing recursion: Show each call as a new row in a trace table. Track the parameter value for each call on the way down (winding), then track return values on the way back up (unwinding). Most exam questions ask you to trace 3–5 calls deep.
Stack overflow from recursion: If a recursive function is called with no base case (or the base case is never reached), the call stack fills up with stack frames until memory is exhausted — this is a stack overflow. It is an error, not an intentional behaviour.
⚠️ Common Mistakes
Forgetting the base case — without it, recursion is infinite and causes a stack overflow
Base case condition is wrong — e.g. using n=1 instead of n=0 for Factorial, causing Factorial(0) to recurse infinitely
Recursive call does not move towards the base case — e.g. calling Factorial(n+1) instead of Factorial(n-1)
Confusing "winding" (calls going deeper) with "unwinding" (returns coming back) when tracing
Stating recursion uses less memory than iteration — recursion uses MORE memory due to the call stack
✅ Notes completed!
▶
Video coming soon
Click slide or press arrow keys to navigate
Worksheet — 2.4.4 Recursion
8 questions · Cambridge 9618 standard
Q1State the two essential components of every recursive routine and explain why each is necessary.[4]
✅ Mark scheme
Base case [1]: a condition under which the function returns a value directly without calling itself — without it, recursion would be infinite [1]; Recursive case [1]: the function calls itself with a modified parameter that moves closer to the base case, solving a smaller version of the problem each time [1].
Q2Trace Factorial(5) through all recursive calls, showing the parameter value and the value returned at each level.[6]
Q3Explain what a 'stack frame' is and why recursive calls use more memory than iterative solutions.[3]
✅ Mark scheme
A stack frame (activation record) is the block of memory pushed onto the call stack for each function call [1]; it stores local variables, parameters, and the return address [1]; recursive calls accumulate stack frames — one for each unresolved call — whereas iterative solutions use a fixed amount of memory for loop variables [1].
Q4A programmer writes: FUNCTION Bad(n) RETURNS INTEGER; RETURN n + Bad(n-1); ENDFUNCTION. State the error and its consequence.[2]
✅ Mark scheme
The function has no base case [1]; this causes infinite recursion — Bad() keeps calling itself indefinitely, filling the call stack until a stack overflow error occurs [1].
Q5Write a recursive Cambridge 9618 pseudocode FUNCTION called SumDown that takes a positive INTEGER n and returns the sum 1 + 2 + ... + n.[4]
✅ Mark scheme
FUNCTION SumDown(n : INTEGER) RETURNS INTEGER [1]; IF n = 1 THEN (or n <= 0) [1]; RETURN 1 (or 0) [1]; ELSE; RETURN n + SumDown(n - 1) [1]; ENDIF; ENDFUNCTION.
Q6State one advantage and one disadvantage of using recursion instead of iteration for the same problem.[2]
✅ Mark scheme
Advantage: recursive code can be simpler/shorter and closer to the mathematical definition of the problem [1]; Disadvantage: recursion uses more memory (due to call stack frames) and has function call overhead, making it slower than an equivalent iterative solution [1].
Q7Write pseudocode to read all lines from a text file called "students.txt", count how many lines contain the word "PASS", and output the count. Use OPENFILE, READFILE, EOF(), and CLOSEFILE correctly.[5]
✅ Mark scheme
DECLARE line : STRING; DECLARE count : INTEGER; count ← 0 — 1 mark; OPENFILE "students.txt" FOR READ — 1 mark; WHILE NOT EOF("students.txt") DO — 1 mark; READFILE "students.txt", line; IF line CONTAINS "PASS" (or suitable string check) THEN count ← count + 1 — 1 mark; ENDWHILE; CLOSEFILE "students.txt"; OUTPUT count — 1 mark.
Q8A student wants to add new records to an existing data file without losing old data. Explain the difference between opening a file FOR WRITE and FOR APPEND, and why APPEND is needed here. What would happen if FOR WRITE were used instead?[4]
✅ Mark scheme
FOR WRITE: creates a new empty file or overwrites an existing file — 1 mark; FOR APPEND: opens an existing file and positions the write pointer at the end — 1 mark; APPEND is needed to add new records while preserving existing ones — 1 mark; using FOR WRITE would erase all existing data in the file — 1 mark.
Topic Quiz
Question 1 of 10
You scored
out of 10
Card 1 of 7
Click to reveal definition
🎉
All cards reviewed!
Term
Definition
🎯
Mini Test — 2.4.4 Recursion
10 questions · 10 marks · 10 minutes
⏱ 10:00
Section A — Multiple Choice [5 marks]
Q1What is the base case in the recursive Factorial function?
Q2What happens when a recursive function has no base case?
Q3What is Factorial(3) using the recursive definition RETURN n * Factorial(n-1)?
Q4Compared to an iterative solution, a recursive solution uses:
Q5In a trace of Factorial(4), how many stack frames are pushed onto the call stack?
Section B — Short Answer [5 marks]
Q6Write the Cambridge 9618 pseudocode for a recursive function that computes n! (n factorial). Include the base case.
Mark schemeFUNCTION Factorial(n : INTEGER) RETURNS INTEGER [1]; IF n = 0 THEN RETURN 1 [1]; ELSE RETURN n * Factorial(n - 1) [1]; ENDIF; ENDFUNCTION [1].
Q7State what is stored in a stack frame when a recursive call is made.
Mark schemeAny two of: local variables [1]; parameter values [1]; return address (where to return to when the call finishes) [1]; return value [1].
Q8Trace Fib(4) step by step. Show each call made and the final returned value. Fib(0)=0, Fib(1)=1, Fib(n)=Fib(n-1)+Fib(n-2).
Q9Give one example of a problem where recursion is particularly natural/suitable compared to iteration.
Mark schemeAny suitable example: traversing a tree (each subtree is a smaller tree — same structure) [1]; merge sort (divide and conquer naturally recursive) [1]; computing Fibonacci numbers [1]; navigating directories/folders in a file system [1]; drawing fractals [1].
Q10Explain why the call stack grows with each recursive call and shrinks as calls return.
Mark schemeEach recursive call is a new function invocation — the system pushes a new stack frame onto the call stack to store that call's local data and return address [1]; the frame must stay on the stack until that call completes and returns its value to the caller [1]; once a call returns, its frame is popped off — LIFO order — so the stack shrinks [1].