Cambridge 9618 · International A Level Computer Science · ~16 min read
Notes
Video
Slides
Quiz
Worksheet
What is Recursion?
Recursion is when a subroutine (function/procedure) calls itself from within its own definition. A recursive algorithm breaks a problem into smaller instances of the same problem until a simple base case is reached.
Every recursive algorithm MUST have:
🛑 Base Case
The condition that STOPS the recursion. Without a base case, the function would call itself infinitely, eventually causing a stack overflow error. The base case returns a direct answer without making another recursive call.
🔁 Recursive Case
The call where the function calls itself with a simpler or smaller version of the problem. Each recursive call must move closer to the base case — otherwise, the recursion never terminates.
Mathematical definition: n! = n × (n-1)! with base case 0! = 1.
// Recursive factorial function FUNCTIONfactorial(n : INTEGER) RETURNS INTEGER IFn = 0THEN// BASE CASE RETURN1 ELSE// RECURSIVE CASE RETURNn * factorial(n - 1) ENDIF ENDFUNCTION
Trace table for factorial(4)
Call
n
n = 0?
Returns
factorial(4)
4
No
4 × factorial(3)
factorial(3)
3
No
3 × factorial(2)
factorial(2)
2
No
2 × factorial(1)
factorial(1)
1
No
1 × factorial(0)
factorial(0)
0
Yes ✓ BASE CASE
1
Unwinding back up:
1×1=1, 2×1=2, 3×2=6, 4×6=24
The Call Stack
Every time a function is called, a stack frame is pushed onto the call stack — it stores the local variables and return address for that call. When the function returns, the frame is popped off. Recursive calls build up many frames:
Call stack during factorial(4)
factorial(4) — n=4, waiting for factorial(3)...
factorial(3) — n=3, waiting for factorial(2)...
factorial(2) — n=2, waiting for factorial(1)...
factorial(1) — n=1, waiting for factorial(0)...
factorial(0) — BASE CASE → returns 1 ✓
↑ After base case returns, each frame unwinds: factorial(1) = 1, factorial(2) = 2, factorial(3) = 6, factorial(4) = 24
If recursion is too deep (no base case, or base case never reached), the stack fills up completely — this causes a stack overflow error (also called "maximum recursion depth exceeded").
Fibonacci Sequence
The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ... — each number is the sum of the two before it.
Mathematical definition: fib(n) = fib(n-1) + fib(n-2), with base cases fib(0) = 0 and fib(1) = 1.
FUNCTIONfibonacci(n : INTEGER) RETURNS INTEGER IFn = 0THEN// BASE CASE 1 RETURN0 ELSE IFn = 1THEN// BASE CASE 2 RETURN1 ELSE// RECURSIVE CASE (two calls!) RETURNfibonacci(n-1) + fibonacci(n-2) ENDIF ENDFUNCTION
⚠️ Fibonacci exponential inefficiency
The naive recursive Fibonacci is extremely inefficient because it recomputes the same values repeatedly. fibonacci(5) computes fibonacci(3) twice, fibonacci(2) three times... The time complexity is O(2ⁿ) — it doubles with each extra n. fibonacci(50) would make ~2⁵⁰ calls (over one trillion!). Solution: memoisation — cache computed values so each is calculated only once, reducing complexity to O(n).
Recursive vs Iterative
🔁 Recursive
Shorter, more elegant code for naturally recursive problems
Each call uses stack space — risk of stack overflow for deep recursion
May be slower due to function call overhead
🔄 Iterative
Uses loops — generally faster and more memory-efficient
No risk of stack overflow
Can be harder to read for inherently recursive problems
Better for: simple counting, linear sequences, performance-critical code
Requires explicit management of state (loop variables)
When to use recursion: when the problem is naturally recursive — i.e. can be defined in terms of smaller versions of itself. Examples: tree traversal, quicksort, merge sort, binary search, parsing expressions, generating permutations.
Tree Traversal with Recursion
Tree traversal is a classic example of a problem that is naturally recursive. Given a binary tree, there are three main traversal orders:
Binary tree traversal
D
/ \
B F
/ \ / \
A C E G
Pre-order (Root, Left, Right): D → B → A → C → F → E → G In-order (Left, Root, Right): A → B → C → D → E → F → G (gives sorted order for BST) Post-order (Left, Right, Root): A → C → B → E → G → F → D
PROCEDUREinOrder(node) IFnode ≠ NULLTHEN inOrder(node.left) // traverse left subtree OUTPUTnode.value // visit root inOrder(node.right) // traverse right subtree ENDIF ENDPROCEDURE
The base case here is implicit: when node = NULL (end of a branch), the procedure simply returns without doing anything. This terminates the recursion naturally.
Cambridge 9618 exam tip: Be able to: write recursive pseudocode with a clear base case and recursive case; trace through recursive calls step by step (trace table); explain what happens on the call stack during recursion and what a stack overflow is; compare recursive vs iterative approaches (pros and cons); write tree traversal in pseudocode — know all three orders (pre/in/post). For Fibonacci: the naive recursive version is exponentially slow; memoisation fixes this. Cambridge exam questions often ask you to "show the contents of the stack" — draw each function call being pushed and popped.
⚠️ Common Mistakes
Forgetting the base case — without it, the function recurses forever and causes a stack overflow. Always check: "what stops this recursion?"
Base case that is never reached — if the recursive case doesn't progress toward the base case (e.g. calls fibonacci(n+1) instead of fibonacci(n-1)), infinite recursion results
Confusing pre-order, in-order, and post-order — remember: the "Root" position tells you the order name (Pre = Root first, In = Root middle, Post = Root last)
Thinking recursive code is always inefficient — it depends on the algorithm. Recursive quicksort and merge sort are efficient O(n log n) algorithms. The naive recursive Fibonacci is inefficient — but fixed with memoisation.
Not being able to trace recursion — practice unwinding the stack: go down until the base case, then work back up multiplying/adding as each call returns
Saying recursion uses a queue — recursion uses the CALL STACK (LIFO). Last in, first out — the deepest call returns first.
✅ Notes completed!
▶
Video coming soon
Click slide or press arrow keys to navigate
Worksheet — 4.1.1 Recursion
8 questions · Cambridge 9618 standard
Q1State what is meant by a "base case" in a recursive algorithm and explain why it is essential.[2]
✅ Mark scheme
The base case is the condition in a recursive algorithm at which the recursion stops — it returns a result directly without making another recursive call [1]; it is essential because without a base case, the function would call itself indefinitely — each call pushes a new stack frame, eventually filling the call stack and causing a stack overflow error [1].
Q2Trace through the call factorial(5) and show the value returned at each level of recursion.[4]
Q3Describe what happens on the call stack during a recursive function call. What is a "stack overflow" and when does it occur?[4]
✅ Mark scheme
Each time a function is called, a stack frame is pushed onto the call stack — it stores the local variables and the return address for that function call [1]; each recursive call adds another frame; when the base case is reached, the stack unwinds — frames are popped one by one as each call returns its result to the caller [1]; a stack overflow occurs when the call stack runs out of memory — the maximum stack depth is exceeded [1]; this happens when there is no base case, the base case is never reached, or the recursion is too deep for very large input values [1].
Q4Write pseudocode for a recursive function that computes the sum of all integers from 1 to n. Include the base case and recursive case.[4]
✅ Mark scheme
FUNCTION sumTo(n : INTEGER) RETURNS INTEGER [1]; IF n = 1 THEN [or n = 0 THEN RETURN 0] — correct base case [1]; RETURN 1 [or 0]; ELSE RETURN n + sumTo(n - 1) — correct recursive case that moves toward base case [1]; ENDIF ENDFUNCTION — properly terminated [1].
Q5State the output of an in-order traversal of this binary tree: root = 10, left child = 5 (with left child = 3), right child = 15 (with right child = 20).[2]
✅ Mark scheme
In-order traversal visits: Left subtree, Root, Right subtree — recursively [1]; traversal: go left from 10 → reach 5 → go left from 5 → reach 3 (no children, output 3) → back to 5 (output 5) → no right child → back to 10 (output 10) → right child 15 → no left child (output 15) → right child 20 (output 20); Output: 3, 5, 10, 15, 20 [1].
Q6Explain why the naive recursive implementation of Fibonacci is inefficient. Describe how memoisation improves this.[4]
✅ Mark scheme
The naive recursive Fibonacci makes two recursive calls for each non-base case (fibonacci(n-1) AND fibonacci(n-2)) — this creates an exponential number of calls [1]; many subproblems are recomputed multiple times — e.g. fibonacci(3) is computed many times when computing fibonacci(6); the time complexity is O(2ⁿ) [1]; memoisation stores the result of each Fibonacci number the first time it is computed in a lookup table (cache) [1]; subsequent calls for the same n simply look up the cached result rather than recursing — reducing time complexity from O(2ⁿ) to O(n) since each value is computed exactly once [1].
Q7Write a recursive FUNCTION BinarySearch(arr : ARRAY, low : INTEGER, high : INTEGER, target : INTEGER) RETURNS INTEGER in Cambridge 9618 pseudocode. It should return the index of target in arr, or −1 if not found. Use DIV for integer division.[4]
✅ Mark scheme
FUNCTION BinarySearch(arr:ARRAY, low:INTEGER, high:INTEGER, target:INTEGER) RETURNS INTEGER [1]; IF low > high THEN RETURN -1 ENDIF (base case — not found) [1]; mid ← (low + high) DIV 2 [1]; IF arr[mid] = target THEN RETURN mid ELSE IF target < arr[mid] THEN RETURN BinarySearch(arr, low, mid-1, target) ELSE RETURN BinarySearch(arr, mid+1, high, target) ENDIF [1].
Q8Trace the execution of Fibonacci(4) where Fibonacci(n) returns Fibonacci(n-1) + Fibonacci(n-2), with base cases Fibonacci(0)=0 and Fibonacci(1)=1. Show the call tree and the final result. State the total number of times Fibonacci(1) is called.[4]
✅ Mark scheme
Fib(4) = Fib(3)+Fib(2) [1]; Fib(3)=Fib(2)+Fib(1), Fib(2)=Fib(1)+Fib(0) [1]; Call tree expands: Fib(4)→3, Fib(3)→2, Fib(2)→1, Fib(2)→1, Fib(1)→1, Fib(1)→1, Fib(0)→0, Fib(1)→1, Fib(0)→0; Final result = 3 [1]; Fibonacci(1) is called 3 times [1].
Topic Quiz
Question 1 of 10
You scored
out of 10
Card 1 of 8
Click to reveal definition
🎉
All cards reviewed!
Term
Definition
🎯
Mini Test — 4.1.1 Recursion
10 questions · 10 marks · 10 minutes
⏱ 10:00
Section A — Multiple Choice [5 marks]
Q1What is the value returned by factorial(3) given: factorial(0)=1 and factorial(n) = n × factorial(n-1)?
Q2What does an in-order traversal of a Binary Search Tree produce?
Q3Why does the naive recursive Fibonacci algorithm have O(2ⁿ) time complexity?
Q4A recursive function with no base case will:
Q5Pre-order traversal visits nodes in which order?
Section B — Short Answer [5 marks]
Q6Explain the difference between the base case and the recursive case in a recursive algorithm. Why must each recursive call progress towards the base case?
Mark schemeThe base case is the terminating condition — the function returns a direct answer without calling itself again [1]; the recursive case is where the function calls itself with a modified (simpler) version of the problem [1]; each recursive call must progress towards the base case (e.g. by reducing n by 1 each time) — if it doesn't, the recursion never reaches the base case, resulting in infinite recursion and a stack overflow [1].
Q7What is memoisation? How does it improve the efficiency of recursive Fibonacci?
Mark schemeMemoisation is a technique where the results of expensive function calls are cached — stored in a lookup table (dictionary/array) the first time they are computed [1]; when the function is called with the same input again, the stored result is returned directly instead of recomputing [1]; for Fibonacci, each value from fib(0) to fib(n) is computed exactly once and cached — subsequent calls look up the result in O(1) time, reducing overall time complexity from O(2ⁿ) to O(n) [1].
Q8Give two advantages of using a recursive solution compared to an iterative one.
Mark schemeAny two from [1 each]: Code is often shorter and more readable/elegant than the iterative equivalent [1]; directly mirrors the mathematical definition of the problem — easier to verify correctness [1]; naturally suited to problems with recursive structure (trees, graphs, divide and conquer algorithms) — an iterative solution would require manually managing a stack [1].
Q9Show the post-order traversal of a binary tree with root B, left child A, and right child C.
Mark schemePost-order traversal visits: Left, Right, Root [1]; A has no children → output A; C has no children → output C; then root B → output B; Post-order output: A, C, B [1].
Q10State two disadvantages of recursion compared to iteration.
Mark schemeAny two from [1 each]: Each recursive call adds a frame to the call stack — deep recursion can cause a stack overflow error; iteration does not have this risk [1]; Function call overhead (pushing/popping stack frames) makes recursion generally slower than an equivalent iterative solution [1]; Harder to debug — tracing through multiple levels of recursion is more complex than following a loop [1].