OCR H446 · A Level Computer Science · ~14 min read
Notes
Video
Slides
Worksheet
Quiz
What is Recursion?
Recursion is a programming technique where a subroutine (function) calls itself as part of its own definition. A recursive solution breaks a problem down into a smaller version of the same problem until it reaches a simple case that can be solved directly.
Every recursive function must have two key components:
Base case: the simplest case that can be solved without further recursion — stops the chain of calls.
Recursive case: the general case where the function calls itself with a simpler/smaller input, working towards the base case.
Classic Example: Factorial
The factorial of n is defined as: n! = n × (n−1) × (n−2) × ... × 1, and 0! = 1.
-- Recursive definition:
factorial(n):
IF n = 0 THEN -- base case
RETURN 1
ELSE -- recursive case
RETURN n * factorial(n - 1)
-- Trace of factorial(4):
factorial(4)
→ 4 * factorial(3)
→ 3 * factorial(2)
→ 2 * factorial(1)
→ 1 * factorial(0)
→ 1 -- base case reached
→ 1 * 1 = 1
→ 2 * 1 = 2
→ 3 * 2 = 6
→ 4 * 6 = 24 -- final answer
The Call Stack
Each time a function calls itself, a new stack frame is pushed onto the call stack. The stack frame stores:
The local variables for that invocation
The return address (where to continue after this call returns)
The parameters passed to this call
When the base case is reached, frames are popped off the stack one by one in reverse order (LIFO), with each returning its value to the frame below it.
If the base case is never reached (missing or incorrect), the stack overflows — a stack overflow error occurs because the system runs out of memory for stack frames.
Second Classic Example: Fibonacci
fibonacci(n):
IF n <= 1 THEN -- base cases: fib(0)=0, fib(1)=1
RETURN n
ELSE
RETURN fibonacci(n-1) + fibonacci(n-2)
-- fib(5) = fib(4) + fib(3)-- fib(4) = fib(3) + fib(2) (overlapping subproblems!)-- This naive recursion has O(2ⁿ) time complexity-- Memoisation or dynamic programming improves to O(n)
Tracing Recursion
Exam questions often ask you to trace a recursive function. Always work through the call stack:
-- Trace mystery(3):
mystery(n):
IF n = 0 THEN RETURN 0
ELSE RETURN n + mystery(n-1)
mystery(3)
= 3 + mystery(2)
= 2 + mystery(1)
= 1 + mystery(0)
= 0 -- base case
= 1 + 0 = 1
= 2 + 1 = 3
= 3 + 3 = 6 -- sum of 1..3
Recursion vs Iteration
Aspect
Recursion
Iteration (loops)
Memory use
Stack frame per call (higher memory)
Single stack frame (lower memory)
Speed
Overhead of function calls
Generally faster
Code clarity
Elegant for naturally recursive problems
Better for simple repeated actions
Risk
Stack overflow if base case missing
Infinite loop if condition wrong
Best use
Trees, graphs, divide & conquer, parsing
Simple counting, linear traversal
Every recursive function can be rewritten iteratively, but for problems that are naturally recursive (tree traversal, quicksort, towers of Hanoi), recursion produces much cleaner code.
Tail Recursion
A function is tail recursive when the recursive call is the very last operation — nothing happens after it returns. Some compilers optimise tail recursion into a loop (tail call optimisation), eliminating stack growth.
-- NOT tail recursive (multiply happens AFTER the call):
factorial(n) = n * factorial(n-1)
-- Tail recursive version (result accumulated in accumulator):
factorial(n, acc):
IF n = 0 THEN RETURN acc
ELSE RETURN factorial(n-1, n * acc)
-- Called as: factorial(4, 1) → factorial(3, 4) → factorial(2, 12) → ...
Real-World Applications of Recursion
File system traversal: exploring a directory tree (each subdirectory is a smaller tree)
Tree and graph traversal: in-order/pre-order/post-order BST traversal; DFS on graphs
Sorting algorithms: Quicksort and Merge sort use divide and conquer recursively
Towers of Hanoi: classic problem requiring recursion — move n discs using 3 pegs
Backtracking algorithms: Sudoku solvers, maze solvers, chess AI move generation
Exam tip: When tracing recursion, draw a call stack diagram — indented calls going down (winding), then values returning upward (unwinding). Always identify the base case first. If asked "what happens without a base case?" → infinite recursion → stack overflow.
Exam tip: You must be able to write and trace recursive algorithms. Common exam questions: write a recursive function for factorial, Fibonacci, or sum(1..n). State the base case and recursive case explicitly. You may also be asked to convert a loop to recursion or explain why recursion uses more memory than iteration.
⚠ Common Mistakes
Forgetting the base case — without it, recursion never terminates and causes a stack overflow.
Tracing recursion in the wrong direction — calls build up FIRST (winding), then values return LAST (unwinding). Do not try to calculate the final answer on the way down.
Confusing "depth" with "iterations" — recursive depth = number of stack frames active simultaneously.
Saying recursion is always slower — tail-recursive functions with compiler optimisation can match iteration.
✓ Notes completed!
▶
Video coming soon
Click to advance · Arrow keys also work
Click slide or press arrow keys to navigate
✍
Worksheet — 1.4.2g Recursion
8 questions · 20 marks · instantly marked
Q1Define recursion. State the two essential components every recursive function must have.[3 marks]
✓ Mark scheme
Recursion: a programming technique where a function (subroutine) calls itself as part of its own definition [1]. Two essential components: (1) Base case — the simplest case that can be solved directly without a further recursive call; it terminates the chain [1]. (2) Recursive case — the general case where the function calls itself with a simpler/smaller input, working towards the base case [1].
Q2Write a recursive function in pseudocode to calculate factorial(n). State clearly the base case and the recursive case.[4 marks]
✓ Mark scheme
factorial(n): [4 marks] IF n = 0 THEN RETURN 1 [base case: 1 mark] ELSE RETURN n * factorial(n - 1) [recursive case: 1 mark] Base case correctly identified as n=0 [1 mark], recursive case multiplies n by factorial(n-1) [1 mark].
Q3Trace the execution of factorial(4) showing the call stack as it winds up and then unwinds. What is the final value returned?[4 marks]
✓ Mark scheme
Winding: factorial(4) → 4×factorial(3) → 3×factorial(2) → 2×factorial(1) → 1×factorial(0) → base case returns 1 [2 marks for correctly showing calls building up]. Unwinding: factorial(0)=1; factorial(1)=1×1=1; factorial(2)=2×1=2; factorial(3)=3×2=6; factorial(4)=4×6=24 [2 marks for correctly computing return values]. Final answer: 24.
Q4What is a stack overflow in the context of recursion? What programming error causes it?[3 marks]
✓ Mark scheme
Stack overflow: when the call stack runs out of available memory because too many stack frames have been pushed onto it without any being popped [1]. It causes a runtime error terminating the program [1]. Cause: infinite recursion — the function never reaches its base case (missing base case, incorrect base case, or base case that is never reached with the given input) [1].
Q5Compare recursion and iteration in terms of: (i) memory usage, (ii) execution speed, (iii) code readability for naturally recursive problems.[3 marks]
✓ Mark scheme
(i) Memory: recursion uses more memory — a new stack frame is allocated per recursive call; iteration uses a single frame [1]. (ii) Speed: recursion is generally slower due to function call overhead (setting up/tearing down stack frames); iteration is faster [1]. (iii) Readability: for naturally recursive problems (trees, graphs, divide-and-conquer), recursion produces clearer, more elegant code that matches the problem structure [1].
Q6Trace the following function and state what it returns for mystery(5):
mystery(n): IF n ≤ 0 THEN RETURN 0 ELSE RETURN n + mystery(n − 2)[3 marks]
Q7What is tail recursion? Give one advantage of using tail-recursive functions.[2 marks]
✓ Mark scheme
Tail recursion: when the recursive call is the very last operation in the function — no computation happens after the recursive call returns [1]. Advantage: compilers/interpreters can optimise tail recursion into a loop (tail call optimisation), eliminating stack frame growth and preventing stack overflows — constant O(1) stack space [1].
Q8Give two real-world computing applications where recursion is naturally used, explaining briefly why each is suited to recursion.[4 marks]
✓ Mark scheme
Any two of: Tree traversal (BST in/pre/post-order) — each subtree is itself a smaller tree, so recursion matches the structure directly [2]. File system traversal — a directory contains files and subdirectories (which contain more files/directories), a naturally recursive structure [2]. Quicksort/Merge sort — divide-and-conquer: sort the left half, sort the right half recursively [2]. Parsing/compilers — expressions are nested (bracket inside bracket), matched by recursive descent parsers [2]. Backtracking (Sudoku, mazes) — try a choice, recurse deeper, undo if it fails [2].
Topic Quiz
1 of 15
You scored
out of 15
🎯
Mini Test — 1.4.2g Recursion
10 questions · 10 marks · 10 minutes
5 MCQ + 5 short answer
⏱10:00
10 marks
Section A — Multiple Choice
Q1What stops a recursive function from running forever?
Q2What happens if a recursive function has no base case?
Q3What is the value of factorial(3) using the recursive definition factorial(n) = n × factorial(n−1), factorial(0) = 1?
Q4Compared to iteration, recursion generally uses:
Q5A tail-recursive function is one where:
Section B — Short Answer
Q6What is a stack frame in the context of recursion?
Mark schemeA stack frame is a block of memory pushed onto the call stack when a function is called. It stores the function's local variables, parameters, and return address (where execution resumes after the function returns). Each recursive call creates a new stack frame. [1 mark]
Q7What does "winding" and "unwinding" mean when tracing recursive calls?
Mark schemeWinding: the phase where recursive calls build up — each call adds a new stack frame until the base case is reached. Unwinding: the phase where return values propagate back up — frames are popped off the stack in LIFO order, each passing its result to the caller above. [1 mark]
Q8State the two base cases for the Fibonacci recursive function.
Mark schemefib(0) = 0 and fib(1) = 1. Two base cases are needed because fib(n) = fib(n-1) + fib(n-2) requires both n-1 and n-2 to eventually reach a known value — the recursion bottoms out at both 0 and 1. [1 mark for both cases]
Q9Give one advantage of using recursion for tree traversal compared to iteration.
Mark schemeTrees are naturally recursive structures (each subtree is itself a tree). Recursion matches this structure directly, producing simpler and more readable code. The iterative alternative would require manually managing a stack data structure to simulate the call stack. [1 mark]
Q10State the value returned by: sum(n): IF n=0 THEN RETURN 0 ELSE RETURN n + sum(n-1), when called as sum(4).
Mark schemesum(4) = 4 + sum(3) = 4+3+sum(2) = 4+3+2+sum(1) = 4+3+2+1+sum(0) = 4+3+2+1+0 = 10. The function computes the sum 1+2+3+4 = 10. [1 mark]