Cambridge Syllabus Notes

19.2 Recursion

Learning Objective

Show understanding of recursion – its definition, structure, execution model, and how it is applied in algorithm design – as required by Cambridge International AS & A Level Computer Science (9618) syllabus point 19.2.

1. What is Recursion?

Recursion is a programming technique in which a method (or function) calls itself, either directly or indirectly, to solve a problem. The original problem is repeatedly reduced to smaller instances of the same problem until a simple case – the base case – can be solved directly.

2. Key Components of a Recursive Method

Base case(s): condition(s) that stop further recursive calls.
Recursive case: the part of the method that reduces the problem and invokes the method again.
Progress towards the base case: each call must move closer to a base case (e.g., by decreasing a counter or narrowing a range) to avoid infinite recursion.

3. How Recursion Works – The Call Stack

When a recursive method is invoked, a new activation record (stack frame) is pushed onto the call stack. A frame typically contains:

Method parameters
Local variables
Return address (where control returns after the call)

When the method returns, its frame is popped and control resumes in the caller’s frame.

Example call‑stack for factorial(4) (ASCII diagram):

+-------------------+   // call factorial(4)
| n = 4             |
| return address → |
+-------------------+
| n = 3             |   // call factorial(3)
| return address → |
+-------------------+
| n = 2             |   // call factorial(2)
| return address → |
+-------------------+
| n = 1             |   // call factorial(1)
| return address → |
+-------------------+
| n = 0             |   // base case reached
| return 1          |
+-------------------+

Frames are popped in reverse order, producing the result 4 × 3 × 2 × 1 = 24.

4. Common Recursive Algorithms (with typical time‑complexity)

Factorial – O(n)
Fibonacci numbers – naive version O(2ⁿ), memoised version O(n)
Binary search – O(log n)
Tree traversals (pre‑order, in‑order, post‑order) – O(n)
Permutations and combinations – O(n · n!) (depends on the specific generation method)

5. Example Implementations (Java)

5.1 Factorial

Mathematical definition:

$$ n! = \begin{cases} 1 & \text{if } n = 0\\[2mm] n \times (n-1)! & \text{if } n > 0 \end{cases} $$

public static long factorial(int n) {
    // base case
    if (n == 0) {
        return 1L;
    }
    // recursive case – progress by decreasing n
    return n * factorial(n - 1);
}

5.2 Naïve Fibonacci

Mathematical definition:

$$ F_n = \begin{cases} 0 & \text{if } n = 0\\[2mm] 1 & \text{if } n = 1\\[2mm] F_{n-1} + F_{n-2} & \text{if } n \ge 2 \end{cases} $$

public static long fib(int n) {
    // base cases
    if (n == 0) {
        return 0L;
    }
    if (n == 1) {
        return 1L;
    }
    // recursive case – two smaller sub‑problems
    return fib(n - 1) + fib(n - 2);
}

Note: Exponential time‑complexity; for large n a memoised or iterative version is preferred.

5.3 Recursive Binary Search

public static int binarySearch(int[] A, int key, int low, int high) {
    // base case – interval empty
    if (low > high) {
        return -1;                     // not found
    }
    int mid = low + (high - low) / 2; // avoid overflow
    if (A[mid] == key) {
        return mid;                    // found
    } else if (key < A[mid]) {
        return binarySearch(A, key, low, mid - 1);   // search left half
    } else {
        return binarySearch(A, key, mid + 1, high); // search right half
    }
}

5.4 In‑order Traversal of a Binary Tree

public static void inorder(Node root) {
    if (root == null) {               // base case
        return;
    }
    inorder(root.left);               // left sub‑tree
    System.out.println(root.data);    // visit node
    inorder(root.right);              // right sub‑tree
}

Node class (simplified):

private static class Node {
    int data;
    Node left, right;
    Node(int d) { data = d; }
}

6. Tail Recursion

A recursive call is in tail position when it is the last operation performed by the method. Some languages can replace the call with a jump (tail‑call optimisation), eliminating extra stack frames. Java does **not** guarantee this optimisation.

Tail‑recursive factorial using an accumulator

public static long factorialTail(int n) {
    return factorialHelper(n, 1L);
}

/* private helper – not part of the public API */
private static long factorialHelper(int n, long acc) {
    if (n == 0) {          // base case
        return acc;
    }
    // tail call – accumulator updated before the recursive call
    return factorialHelper(n - 1, n * acc);
}

The helper method is private because it is an implementation detail; the public API remains simple, matching typical Cambridge exam expectations.

7. Advantages and Disadvantages of Recursion

Aspect	Recursion	Iteration
Code clarity for divide‑and‑conquer problems	Usually mirrors the mathematical definition; concise.	Often more verbose; explicit stack or auxiliary data structures needed.
Memory usage	One stack frame per call (depth = number of recursive levels). Typical worst‑case space = O(n).	Constant stack space; any extra memory is explicit (e.g., arrays).
Performance overhead	Function‑call overhead at each level.	Loop control overhead is minimal.
Tail‑call optimisation	Possible only if language/runtime guarantees it (Java does not).	Not applicable.
Ease of proving correctness	Inductive proofs align directly with the recursive definition.	Requires loop invariants; can be less intuitive.

Key Advantages

Clear mapping to mathematical definitions (e.g., factorial, tree traversals).
Implicit stack management – the runtime handles it.
Facilitates correctness proofs using mathematical induction.
When supported, tail‑call optimisation can give the efficiency of iteration.

Key Disadvantages

Each call consumes stack space; deep recursion may cause a stack overflow (Java’s default depth is only a few thousand calls).
Function‑call overhead can make recursive solutions slower than equivalent loops.
Java does **not** guarantee tail‑call optimisation, so even tail‑recursive code may use extra frames.
Some problems are naturally expressed with simple loops, making iteration more efficient.

8. Common Pitfalls

Missing or incorrect base case – leads to infinite recursion.
Not moving towards the base case (e.g., calling with the same argument).
Assuming recursion is always faster – overhead may make it slower.
Ignoring stack‑depth limits – typical Java stack overflows after a few thousand calls.
Incorrect handling of invalid inputs (e.g., factorial(-1) or negative indices in binary search).

9. Exam Tips for A‑Level 9618

Identify whether the problem naturally splits into smaller sub‑problems; if not, an iterative solution may be preferred.
Before writing code, state the base case(s) in words and explain why they stop the recursion.
Show a small trace of the call stack for at least one example (e.g., factorial(3) or binary search on a 5‑element array). Use a diagram or a numbered list of frames.
If asked to convert recursion to iteration, replace the implicit call stack with an explicit while/for loop and any required accumulator variables.
Always mention time‑complexity (e.g., O(2ⁿ) for naïve Fibonacci) and space‑complexity (usually O(n) for recursion depth).
Remember that Java does **not** guarantee tail‑call optimisation – you may be asked to discuss this limitation.

10. Summary

Recursion is a powerful technique for problems that can be expressed as smaller instances of the same problem. Mastery for the Cambridge A‑Level exam requires:

Clear definitions of recursion, base case, recursive case, and progress towards the base case.
Understanding of the call‑stack mechanism (parameters, locals, return address).
Ability to write correct Java methods that follow Cambridge’s visibility conventions.
Awareness of advantages, disadvantages, and the limits of tail‑call optimisation in Java.
Skill in tracing recursive calls, analysing complexity, and converting between recursive and iterative forms.

With regular practice, students can confidently choose the most appropriate solution method and present it clearly in the exam.

11. Action‑Oriented Review Checklist

Use this table to audit your lecture‑note packet against the Cambridge International AS & A Level Computer Science (9618) syllabus for 2026.

Syllabus Area	What to Verify in the Notes	Typical Gaps & How to Fix Them
1. Information Representation (binary, BCD, ASCII/Unicode, hex, two’s‑/one’s‑complement, overflow)	• All number‑base conversions are shown with worked examples. • Binary arithmetic (addition, subtraction) demonstrated step‑by‑step. • BCD and hexadecimal use‑cases explained.	Missing: concrete conversion tables, overflow illustration. Fix: add a short “conversion cheat‑sheet” and a worked 8‑bit two’s‑complement overflow example.
2. Multimedia (Graphics & Sound) & Compression	• Bitmap vs. vector encoding, colour‑depth, resolution calculations. • Sampling‑rate & bit‑depth impact on audio file size. • Lossy vs. loss‑less methods (RLE, JPEG, MP3) with justification examples.	Missing: file‑size estimation formulae, real‑world justification (why choose JPEG for photos, PNG for icons). Fix: insert a quick calculation box and a “choose the right format” decision table.
3. Communication & Networks	• LAN/WAN characteristics, client‑server vs. peer‑to‑peer, thin‑/thick‑client. • Topologies (bus, star, mesh, hybrid) with pros/cons. • IP addressing (IPv4/IPv6), subnetting, DNS, URL anatomy. • Ethernet/CSMA‑CD, wired vs. wireless, bit‑streaming concepts.	Missing: subnet mask example, DNS lookup flow, cloud‑computing overview. Fix: add a subnet‑mask worksheet and a short “cloud‑vs‑local” comparison graphic.
4. Hardware & Processor Fundamentals	• CPU architecture (Von Neumann, registers, ALU, CU, clock, bus types). • Fetch‑Execute cycle diagram with register‑transfer notation. • Logic gates & truth tables, simple circuit design. • Assembly language basics (addressing modes, two‑pass assembler). • Bit‑manipulation (shifts, masks).	Missing: pipeline vs. non‑pipeline illustration, interrupt handling flow, example assembly program with comments. Fix: add a 5‑stage pipeline schematic and a short annotated assembly snippet (e.g., load‑add‑store).
5. System Software	• OS roles (memory, file, process, device management) and utility examples. • Language translators (assembler, compiler, interpreter) with pros/cons. • IDE features (syntax checking, debugging).	Missing: explanation of dynamic linking (DLLs) and a simple compiler‑vs‑interpreter decision matrix. Fix: insert a “when to use a compiler vs. an interpreter” table.
6. Security, Privacy & Data Integrity	• Threat types (malware, phishing, social engineering). • Countermeasures (encryption, hashing, digital signatures, firewalls). • Legal & ethical considerations (data protection, privacy laws).	Missing: real‑world case study and a checklist for secure coding practices. Fix: add a brief case study (e.g., password‑hash breach) and a “secure coding checklist” box.

Run through this checklist after each topic to ensure full coverage and to spot any gaps before the exam.

Show understanding of recursion