Recursion and Advanced Algorithms
Recursion is a technique in which a subroutine calls itself, directly or indirectly, to solve a smaller version of the same problem, until it reaches a base case where it can return an answer without calling itself again. Every recursive call adds a new stack frame to the call stack, holding that call's own parameters and local variables separately from every other active call; frames are removed in last-in-first-out (LIFO) order as each call finishes, which is when any calculation waiting on that call's result is completed. The Tower of Hanoi puzzle, moving n disks between pegs one at a time without ever placing a larger disk on a smaller one, is a classic recursive algorithm: it solves the n-disk problem by recursively solving two (n-1)-disk sub-problems either side of moving the single largest disk.
Before you start
Make sure you're comfortable with these topics first:
Method
- Identify the base case first: the smallest/simplest version of the problem that can be answered directly, with no further recursive call.
- Identify the recursive case: how the problem is reduced to a smaller version of itself, and exactly what changes in the parameters passed to the next call so it moves closer to the base case.
- Trace a recursive call by drawing a new stack frame each time the subroutine calls itself, recording that frame's own copy of every parameter and local variable, and only removing (popping) a frame once its call has returned a value.
- When a recursive function needs to combine results from deeper calls (e.g. n + Factorial(n-1)), work down to the base case first, then work back up the stack, completing each pending calculation as its frame is popped.
- Compare a recursive solution with an equivalent iterative (loop-based) one: recursion often reads more like the original problem definition, but each active call uses extra memory for its own stack frame, whereas a loop reuses the same variables.
- For the Tower of Hanoi, solve MoveDisks(n, from, to, via) by recursively calling MoveDisks(n-1, from, via, to), then physically moving the single largest disk from 'from' to 'to', then recursively calling MoveDisks(n-1, via, to, from).
- Check any recursive subroutine will actually terminate: confirm every recursive call's parameters move strictly closer to the base case, so the recursion cannot run forever.
Worked example
A recursive function is defined as: FUNCTION Factorial(n : INTEGER) RETURNS INTEGER IF n = 0 THEN RETURN 1 ELSE RETURN n * Factorial(n - 1) ENDIF ENDFUNCTION Trace the call Factorial(4), showing how the call stack builds up and then unwinds, and state the value returned.
- Call Factorial(4): n=4 is not the base case, so this call pushes a new stack frame and waits on the result of Factorial(3) before it can compute 4 * Factorial(3).
- This repeats for Factorial(3), Factorial(2) and Factorial(1): each pushes its own stack frame and waits on the next call down, since none of them have reached n=0 yet.
- Call Factorial(0): n=0 is the base case, so this call returns 1 immediately, with no further recursive call.
- The stack now unwinds: Factorial(1)'s frame resumes and computes 1 * Factorial(0) = 1 * 1 = 1, then returns 1 and is popped.
- Factorial(2) resumes and computes 2 * Factorial(1) = 2 * 1 = 2, then Factorial(3) resumes and computes 3 * Factorial(2) = 3 * 2 = 6.
- Factorial(4) resumes and computes 4 * Factorial(3) = 4 * 6 = 24. Final answer: Factorial(4) returns 24, and its stack frame is the last to be popped.
Practice questions
Type your answer and press Check to be marked straight away, or reveal the answer and mark yourself.
Q1State what is meant by the 'base case' of a recursive subroutine.Show answer
Answer: The case (condition on the parameters) simple enough for the subroutine to return an answer directly, without making any further recursive call.
Q2Explain why a recursive subroutine that never reaches its base case is a problem.Show answer
Answer: It will keep calling itself indefinitely (infinite recursion), pushing an ever-growing number of stack frames onto the call stack until the available memory is exhausted, causing a stack overflow (crash).
Q3State what a 'stack frame' stores for one active recursive call.Show answer
Answer: That call's own copy of its parameters and local variables, kept separate from every other active call of the same subroutine.
Q4State the order in which stack frames are removed from the call stack as recursive calls return.Show answer
Answer: Last-in-first-out (LIFO): the most recently pushed (most deeply nested) call's frame is always the first to be popped.
Q5A recursive function Sum(n) is defined as: IF n = 0 THEN RETURN 0 ELSE RETURN n + Sum(n - 1). State the value returned by Sum(3).Show answer
Answer: 6 (Sum(3) = 3 + Sum(2) = 3 + (2 + Sum(1)) = 3 + (2 + (1 + Sum(0))) = 3 + 2 + 1 + 0 = 6).
Q6In the Tower of Hanoi puzzle, state the one rule about disk size that must never be broken when moving a disk.Show answer
Answer: A larger disk must never be placed on top of a smaller disk.
Q7State the minimum number of individual disk moves needed to solve the Tower of Hanoi puzzle for n = 3 disks, using the formula 2^n - 1.Show answer
Answer: 7 (2^3 - 1 = 8 - 1 = 7).
Q8State one advantage an iterative (loop-based) solution has over an equivalent recursive solution.Show answer
Answer: An iterative solution does not create a new stack frame for every repetition, so it generally uses less memory and avoids any risk of a stack overflow for a large number of repetitions.
Exam-style questions
Written in the style of a A Level Computer Science exam paper, with a full mark scheme.
A recursive subroutine is written to calculate the sum of a list of numbers, but the programmer has forgotten to include a base case. Explain what will happen when this subroutine is run, and state the general term used to describe this fault.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 3 available
A recursive function is defined as: FUNCTION Fib(n : INTEGER) RETURNS INTEGER IF n <= 1 THEN RETURN n ELSE RETURN Fib(n - 1) + Fib(n - 2) ENDIF ENDFUNCTION (a) State the value returned by Fib(4). (2 marks) (b) By drawing or describing the full tree of recursive calls made while evaluating Fib(4), state the total number of times Fib is called altogether (including the original call), and the number of these calls that reach the base case directly. (4 marks)
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 6 available
The following recursive procedure solves the Tower of Hanoi puzzle, moving n disks from peg 'from' to peg 'to', using peg 'via' as the spare peg: PROCEDURE Hanoi(n : INTEGER, from : STRING, to : STRING, via : STRING) IF n = 1 THEN OUTPUT "Move disk 1 from ", from, " to ", to ELSE Hanoi(n - 1, from, via, to) OUTPUT "Move disk ", n, " from ", from, " to ", to Hanoi(n - 1, via, to, from) ENDIF ENDPROCEDURE The call Hanoi(3, "A", "C", "B") is made, to move 3 disks from peg A to peg C using peg B as the spare. Trace the procedure and state, in order, every move it outputs.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 7 available
See real A Level Computer Science past-paper questions, with official mark schemes →
Free printable worksheet
Want more practice on paper? Download the recursion and advanced algorithms worksheet pack - 16 pages of exam-style questions with a full mark scheme. One email opens every download in this browser for 14 days - no account, no card. Print it for personal and classroom use.
Next topics
Not quite what you needed?
Tell us what is missing on recursion and advanced algorithms, or which topic to write up next. Every request is read, and we reply to every one.
Build a full practice pack.
This topic is one of hundreds in the library - pick the ones a student needs and generate a printable PDF in minutes.