Skip to topic
    ← Back to course topics

    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

    1. 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
    1. 1Day 1-3: Master basic mathematical recursive patterns (factorials, Fibonacci) by hand-tracing stack frames step-by-step.
    2. 2Day 4-6: Write recursive pseudocode for data structure operations, specifically pre-order, in-order, and post-order binary tree traversals.
    3. 3Day 7-9: Complete past AQA exam questions comparing recursion and iteration regarding time complexity, memory overhead, and maintainability.
    4. 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)
    Trace

    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.

    Compare

    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)
    Pitfall: Failing to explain how recursion utilises the call stack when tracking memory usage during recursive calls.
    ❌ Weak Answer (Loses Marks):Recursion takes up lots of RAM because it repeats lines of code many times.
    Example improved answer:Each recursive call allocates a new stack frame on the call stack containing return addresses, parameters, and local variables. Excessive recursion consumes memory linearly with recursion depth, risking a stack overflow error if the base case is not reached.
    Examiner Tip: Always specify the contents of a stack frame (parameters, local variables, return address) when discussing memory consumption in recursive algorithms.
    Pitfall: Omitting the base case or defining a base case condition that cannot mathematically be reached.
    ❌ Weak Answer (Loses Marks):The function keeps calling itself with n - 1 until it stops at the end.
    Example improved answer:The subroutine must define a stopping condition known as a base case, which evaluates without making a recursive call. If n decreases by 1 on each step, the base case must check if n <= 0 or n == 1 to guarantee termination.
    Examiner Tip: State clearly both the base case and the recursive step when writing or explaining pseudocode for recursive subroutines.
    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. 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. 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. 3.Step 3: Reach base case at mystery(1), returning 1 without further recursive calls.
    4. 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.
    Final Answer: mystery(4) evaluates to 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. 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. 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. 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. 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.
    Final Answer: Recursion provides concise, natural code for tree traversal but incurs significant call stack memory overhead (O(h)), whereas iteration requires explicit data structures and complex logic but avoids stack overflow limitations.
    Active Recall Memory Test
    What three items are stored inside a stack frame on the call stack during a recursive call?
    Key Fact: The return address, parameter values passed to the routine, and local variables.
    What occurs mechanically to cause a stack overflow error during recursion?
    Key Fact: Too many nested recursive calls are pushed onto the call stack without hitting a base case, exhausting the stack memory limit.
    Why is recursion considered more natural than iteration for binary tree traversal?
    Key Fact: Binary trees are recursive data structures (a node points to subtrees that are themselves binary trees), making self-referential subroutines directly mirror their structure.
    Frequently Asked Questions
    Can every recursive algorithm be converted into an iterative one?
    Yes, any recursive algorithm can theoretically be rewritten using iteration. However, doing so often requires manually managing an explicit stack data structure (such as in iterative tree traversals) to track states that the system call stack normally handles automatically. While the iterative version uses memory on the heap and avoids call stack overflow, the code is frequently longer and harder to maintain.
    What is tail recursion and why does it matter?
    Tail recursion occurs when the recursive call is the very last operation performed by the subroutine, meaning there is no pending calculation to perform after the call returns. Some modern compilers can optimise tail-recursive functions into equivalent iterative loops behind the scenes (tail-call optimisation). This reuses the current stack frame rather than creating new ones, completely preventing stack overflow errors.
    Why is the base case so critical in recursive code?
    The base case provides a direct, non-recursive answer for the smallest unit of the problem. Without a properly reachable base case, the function continues invoking itself infinitely until system memory is exhausted, raising a stack overflow runtime exception. It is the definitive stopping mechanism that allows call stack unwinding to begin.
    How do examiners test recursion in AQA A-Level Computer Science papers?
    Examiners commonly test recursion through dry-run trace tables where you follow values down to the base case and back up. They also set questions requiring you to identify missing base cases in buggy pseudocode or write 6-mark comparative essays contrasting the memory efficiency and maintainability of recursion versus iteration. You should be prepared to discuss the call stack explicitly.