Show understanding of recursion

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)

1. Factorial – O(n)
2. Fibonacci numbers – naive version O(2ⁿ), memoised version O(n)
3. Binary search – O(log n)
4. Tree traversals (pre‑order, in‑order, post‑order) – O(n)
5. 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

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

1. Identify whether the problem naturally splits into smaller sub‑problems; if not, an iterative solution may be preferred.
2. Before writing code, state the base case(s) in words and explain why they stop the recursion.
3. 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.
4. If asked to convert recursion to iteration, replace the implicit call stack with an explicit while/for loop and any required accumulator variables.
5. Always mention time‑complexity (e.g., O(2ⁿ) for naïve Fibonacci) and space‑complexity (usually O(n) for recursion depth).
6. 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.

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