Show understanding of recursion

19.2 Recursion

Learning Objective

Show understanding of recursion, its structure, execution model and how it is applied in algorithm design.

What is Recursion?

Recursion is a programming technique where a method or function calls itself directly or indirectly in order to solve a problem. The problem is divided into smaller sub‑problems of the same type until a simple case – the base case – can be solved directly.

Key Components of a Recursive Method

• Base case: The condition that stops further recursive calls.
• Recursive case: The part of the method that reduces the problem and calls the method again.
• Progress towards the base case: Each call must move closer to the base case to avoid infinite recursion.

How Recursion Works – The Call Stack

Each time a recursive method is invoked, a new activation record (stack frame) is placed on the call stack. When a method returns, its frame is removed, and control returns to the caller.

Common Recursive Algorithms

1. Factorial
2. Fibonacci numbers
3. Binary search
4. Tree traversals (pre‑order, in‑order, post‑order)
5. Permutations and combinations

Example 1 – Factorial

The factorial of a non‑negative integer \$n\$ is defined as:

\$\$ n! =

\begin{cases}

1 & \text{if } n = 0 \\

n \times (n-1)! & \text{if } n > 0

\end{cases} \$\$

Java implementation:

public static long factorial(int n) {
if (n == 0) {                 // base case
return 1;
} else {                      // recursive case
return n * factorial(n-1);
}
}

Example 2 – Fibonacci Numbers

The \$n^{\text{th}}\$ Fibonacci number \$F_n\$ is defined by:

\$\$ F_n =

\begin{cases}

0 & \text{if } n = 0 \\

1 & \text{if } n = 1 \\

F{n-1} + F{n-2} & \text{if } n \ge 2

\end{cases} \$\$

Simple recursive Java method (inefficient for large \$n\$):

public static long fib(int n) {
if (n == 0) return 0;          // base case 1
if (n == 1) return 1;          // base case 2
return fib(n-1) + fib(n-2);    // recursive case
}

Example 3 – Binary Search (Recursive)

Searches a sorted array \$A\$ for a key \$k\$ between indices \$low\$ and \$high\$.

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

Advantages of Recursion

• Elegant and concise code for problems that have a natural recursive structure (e.g., trees, divide‑and‑conquer).
• Reduces the need for explicit stack management.
• Often easier to reason about correctness using mathematical induction.

Disadvantages of Recursion

• Each call consumes stack space; deep recursion can cause stack overflow.
• Overhead of function calls may make recursive solutions slower than iterative equivalents.
• Some problems are more naturally expressed iteratively (e.g., simple loops).

Tail Recursion

A recursive call is in tail position if it is the last operation performed by the method. Compilers or interpreters can optimise tail recursion into iteration, eliminating additional stack frames.

Example of tail‑recursive factorial (using an accumulator):

public static long factorialTail(int n) {
return factorialHelper(n, 1);
}
private static long factorialHelper(int n, long acc) {
if (n == 0) {
return acc;                     // base case
}
return factorialHelper(n-1, n * acc); // tail call
}

Recursion vs Iteration – Comparison Table

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 – it can be slower due to overhead.
• Ignoring stack depth limits – typical Java stack depth is a few thousand calls.

Exam Tips for A‑Level 9618

1. Identify whether the problem naturally splits into smaller sub‑problems.
2. Clearly state the base case(s) and recursive case in your answer.
3. Show a small trace of the call stack for at least one example (e.g., factorial(3)).
4. When asked to convert recursion to iteration, replace the call stack with an explicit loop and any required variables.
5. Remember to discuss time‑complexity (often \$O(2^n)\$ for naive Fibonacci) and space‑complexity (usually \$O(n)\$ for depth of recursion).

Summary

Recursion is a powerful tool for solving problems that can be expressed in terms of smaller instances of the same problem. Mastery involves recognising suitable problems, writing correct base and recursive cases, understanding the call stack, and being aware of performance implications. With practice, students can choose between recursive and iterative solutions appropriately for the Cambridge A‑Level Computer Science exam.