Recursive techniques — AQA A-Level Computer Science
A recursive technique is a programming method where a subroutine calls itself directly or indirectly to solve a problem broken into smaller identical sub-problems. Every valid recursive routine requires a base case to terminate execution and prevent call stack overflow, alongside a general recursive step.
Recursive techniques explained
Recursion is a technique in which a subroutine calls itself to solve a problem by reducing it to smaller instances of the same problem.
Read the full explanation
A correct recursive solution has a base case, which returns a result directly without further recursion, and a general (recursive) case, which reduces the problem and calls the subroutine again. For example, factorial(n) has the base case factorial(0) = 1 and the general case n × factorial(n − 1). Each recursive call pushes a new stack frame, and the calls unwind as each base or returned value is passed back up. Without a base case, the calls never terminate and the stack eventually overflows. Learners should be able to identify both cases in a given subroutine and trace how the mechanism of stack frames implements the repeated calls.
Your focus
- Be familiar with the use of recursive techniques in programming languages (general and base cases and the mechanism for implementation).
Recursive techniques exam tips
Topic Overview
Recursive techniques involve subroutines calling themselves to break complex, self-similar problems down into simpler instances until a trivial base case is reached. This paradigm is fundamental to dividing and conquering algorithmic challenges, such as Quicksort, Mergesort, and depth-first binary tree traversals.
Understanding recursion requires mastering the underlying hardware and memory operations, specifically how the call stack stores activation records for each invocation. In AQA A-Level Computer Science, students must be capable of tracing recursive routines, calculating their space and time complexity, and evaluating when to choose iteration over recursion.
Key Concepts
- →Base case: The termination condition that yields an immediate value without triggering further recursive calls.
- →Call stack & stack frames: Memory structures that dynamically store return addresses, parameter values, and local variables for each active invocation.
- →Call stack unwinding: The sequential popping of stack frames and propagation of returned values back up through parent subroutine calls.
- →Stack overflow: A runtime error occurring when recursive calls exceed the maximum allocated memory depth of the system call stack.
Marking Points
- Identifies the base case as the condition that stops further recursive calls and returns a value directly.
- Identifies the general case as the step that reduces the problem and calls the subroutine again.
- Explains that each recursive call creates a new stack frame, implementing the mechanism of repeated calls.
- Describes the unwinding of frames as results return to earlier calls.
Examiner Tips
- 💡Always state both the base case and the general case when asked to describe recursion.
- 💡Trace factorial(3) through the calls to show how values return up the stack.
- 💡Link the mechanism to stack frames rather than describing recursion vaguely.
- 💡Always draw a stack trace diagram showing stacked activation records when exam questions ask you to trace or debug a recursive algorithm.
- 💡When asked for the three essential parts of a recursive subroutine, clearly state: a base case, a general (recursive) case, and progress toward the base case in each recursive call.
Common Mistakes
- States that the base case is the first line of code in the subroutine; correct by identifying it as the condition that halts the recursion.
- Omits the base case, leading to infinite recursion; correct by always defining a condition that stops the calls.
- Believes recursive calls share one set of local variables; correct by explaining each call has its own stack frame.
- Believing that recursion is always faster than iteration; in reality, recursion incurs significant CPU overhead due to repeated subroutine call instructions and stack frame allocations.
- Assuming every recursive call executes concurrently; each call halts the execution of its caller until the base case returns and the call stack unrolls sequentially.
- Thinking recursive code does not use additional memory; even if local variables are minimal, each recursive depth consumes memory via its activation record on the call stack.
Revision Plan
- 1Day 1-3: Master basic mathematical recursive patterns (factorials, Fibonacci) by hand-tracing stack frames step-by-step.
- 2Day 4-6: Write recursive pseudocode for data structure operations, specifically pre-order, in-order, and post-order binary tree traversals.
- 3Day 7-9: Complete past AQA exam questions comparing recursion and iteration regarding time complexity, memory overhead, and maintainability.
- 4Day 10: Timed practice tracing recursive trace-table questions with nested conditionals.
Exam Question Types
- 📋Trace and output prediction: Given recursive pseudocode, track parameter changes across recursive calls and state the final returned string or integer.
- 📋Code writing and completion: Complete or construct a recursive subroutine (e.g. searching a linked list or traversing a tree) incorporating correct base and recursive cases.
- 📋Comparative analysis essays: Contrast recursive and iterative approaches for a given scenario focusing on readability, stack safety, and execution efficiency.
Command Word Expectations (AQA)
Follow the step-by-step execution of code sequentially, recording variable states and return values accurately across every recursive layer, often using a trace table.
Identify both similarities and differences between two approaches (e.g. recursion vs iteration), addressing specific criteria such as memory usage, readability, and performance.
How Students Lose Marks (Examiner Pitfalls)
Step-by-Step Worked Solutions
Question: Trace the execution of the recursive function 'mystery(4)' where 'mystery(n)' is defined as: if n <= 1 return 1, else return n * mystery(n - 1). Show the call stack unwinding.
- 1.Step 1: Identify the base case and recursive relation. Base case is n <= 1 returning 1; recursive step evaluates n * mystery(n - 1).
- 2.Step 2: Trace initial push operations onto the call stack. mystery(4) calls 4 * mystery(3); mystery(3) calls 3 * mystery(2); mystery(2) calls 2 * mystery(1).
- 3.Step 3: Reach base case at mystery(1), returning 1 without further recursive calls.
- 4.Step 4: Unwind the stack by substituting returned values: mystery(2) returns 2 * 1 = 2; mystery(3) returns 3 * 2 = 6; mystery(4) returns 4 * 6 = 24.
Question: Compare the use of recursion versus iteration for tree traversal algorithms in terms of code complexity and system resource usage. (6 marks)
- 1.Step 1: Address code complexity and expressiveness. Tree traversal (e.g. pre-order, in-order) is naturally hierarchical. Recursive definitions mirror the recursive structure of trees, producing elegant, concise, and self-documenting code with fewer lines compared to manual iteration.
- 2.Step 2: Address system resource overhead. Recursive traversals place a stack frame on the call stack for each visited level of depth. This incurs memory overhead proportional to the tree height (O(h)), which in degenerate/unbalanced trees can risk stack overflow.
- 3.Step 3: Compare with iterative alternatives. Iterative traversals require an explicitly managed auxiliary stack data structure to track backtracking, which increases code complexity and programmer error potential, though it avoids hardware call stack size limits.
- 4.Step 4: Formulate a balanced conclusion. Recursion is preferred for readability and natural problem alignment in balanced trees, whereas iteration is safer when processing extremely deep or arbitrarily unbalanced structures.