Loading…
Free A-Level Computer Science guide
A recursive function solves a problem using a smaller instance of itself. Learn to prove that it stops, trace the waiting calls and compare it with a loop. Written for OCR A-Level H446, with original Python examples and practice.
Content owner: Michael Print · Written for A-Level learners · Checked against official specifications
Recursion occurs when a subroutine calls itself, directly or through other subroutines. A terminating solution needs a base case and recursive steps that move towards it for every supported input.
The base case supplies an answer without another recursive call. Each other call solves a smaller instance, then uses its returned answer to finish its own work.
Each call has its own parameters and local variables. The call stack retains the information needed to resume a waiting caller. When a base case returns, the waiting calls finish in reverse order: this is unwinding.
A reliable trace has two parts: write the calls going down towards the base case, then calculate the results returning up.
You should understand a function call, a parameter, a local variable and a return value. Revisit Python lists and functions and selection and loops if needed.
Scope: OCR H446 §2.2.1(b). Our factorial inputs are integers greater than or equal to 0. Python uses a finite recursion limit, so these examples are intended for small inputs.
Factorial multiplies the positive integers up to a number: 4! = 4 × 3 × 2 × 1 = 24. The definition 0! = 1 supplies our stopping case.
Check the base case
If n = 0, return 1 immediately. There is no smaller call.
Call on a smaller input
For positive n, request factorial(n − 1). Keep this call’s n while waiting.
Finish when the answer returns
Multiply the returned answer by this call’s n, then return that product: n! = n × (n − 1)!.
def factorial_recursive(n):
# Precondition: n is an integer.
if n < 0:
raise ValueError("n must be non-negative")
if n == 0:
return 1
return n * factorial_recursive(n - 1)
def factorial_iterative(n):
# Precondition: n is an integer.
if n < 0:
raise ValueError("n must be non-negative")
result = 1
for value in range(1, n + 1):
result = result * value
return result
print(factorial_recursive(4)) # 24
print(factorial_recursive(0)) # 1
print(factorial_iterative(4)) # 24
print(factorial_iterative(0)) # 1Decreasing a non-negative integer by 1 must reach 0. Starting below 0 and repeatedly subtracting 1 would move away from the base case instead.
Both functions reject negative integers with ValueError. They assume integer inputs; neither is a general validator for other types.
Worked example
The first call cannot finish 4 × factorial_recursive(3) until the smaller call returns. The same happens at 3, 2 and 1. The call at 0 immediately returns 1.
Reaching the base case supplies 1; the waiting callers still need to finish their multiplications. Work back up from the most recent call:
1 × 1 = 1.2 × 1 = 2.3 × 2 = 6.4 × 6 = 24.| Call made | Active calls, oldest to newest | Work waiting in the caller |
|---|---|---|
| factorial(4) | 4 | No caller in this function |
| factorial(3) | 4 → 3 | At 4: multiply result by 4 |
| factorial(2) | 4 → 3 → 2 | At 3: multiply result by 3 |
| factorial(1) | 4 → 3 → 2 → 1 | At 2: multiply result by 2 |
| factorial(0) | 4 → 3 → 2 → 1 → 0 | At 1: multiply result by 1 |
| Call finishing | Result returned | Calls still waiting |
|---|---|---|
| 0 | 1 | 4 → 3 → 2 → 1 |
| 1 | 1 | 4 → 3 → 2 |
| 2 | 2 | 4 → 3 |
| 3 | 6 | 4 |
| 4 | 24 | None in factorial |
A stack frame represents one call. Making the call at 3 does not overwrite the waiting call's n = 4: each frame keeps its own state.
This is a simplified examination model of a call frame.
The newest call finishes first: last in, first out. This trace reaches five simultaneous frames, including the call at 0. Code with a base case at 1 would give a different count, so check the supplied function.
| Feature | Recursive version | Iterative version |
|---|---|---|
| How repetition happens | New call with n − 1 | Loop through 1 to n |
| How it stops | Base case n = 0 | Loop exhausts its range |
| Time growth | O(n) | O(n) |
| Auxiliary space growth | O(n) waiting call frames | O(1) fixed working variables |
| Extra overhead | Function calls and returns | Loop control |
These costs assume fixed-cost arithmetic and fixed-size integer values; real large factorials use increasingly large integers. The key difference here is the recursive version's chain of waiting frames.
Recursion often describes tree traversal or divide and conquer clearly because the smaller problems have the same structure. A simple loop is usually a practical choice for this factorial calculation.
An iterative replacement for a recursive tree algorithm might need an explicit stack, so iteration does not automatically mean constant space. Python does not eliminate the frames of these recursive calls. A sufficiently deep chain can raise RecursionError, even with a logically correct base case.
These four original questions total 18 marks. The allocation is our indicative guidance, not an OCR mark scheme. Equivalent correct explanations and code are acceptable.
def sum_down(n):
# Precondition: n is a non-negative integer.
if n == 0:
return 0
return n + sum_down(n - 1)
print(sum_down(3)) # 6Trace sum_down(3) using the code above. Give the calls in order and the value returned by each call as the stack unwinds.
Indicative answer:
sum_down(3), sum_down(2), sum_down(1), sum_down(0), in that order (1).The final printed value is 6; this is the last return already credited.
A learner changes the final line of sum_down to return n + sum_down(n + 1). Explain what happens for input 2, correct the line and explain why the corrected version terminates.
Indicative answer:
n == 0 (1).return n + sum_down(n - 1) (1).Write a recursive Python function list_total(values) that returns the sum of a list of integers. Return 0 for an empty list. Use a smaller list on each recursive call. You may assume all list items are integers.
Indicative answer: Award one mark for each feature:
values and a returned result.One approach:
def list_total(values):
if len(values) == 0:
return 0
return values[0] + list_total(values[1:])
print(list_total([2, 5, 4])) # 11
print(list_total([])) # 0This is a clear teaching version, but Python slicing makes new lists. An index parameter can avoid those copies; do not infer factorial's space cost for every recursive function.
Compare the time and auxiliary space complexity of the two factorial functions on this page. Use the unit-cost arithmetic model and explain the difference in space use.
Indicative answer:
Checked against OCR H446 specification version 3.0 (2026), printed page 12: §2.2.1(b), recursion and comparison with iteration. Examples and practice questions are independently written.
Code checked with Python 3.12.14. Content reviewed 10 October 2026; editorial draft awaiting tutor approval.
These are independently written explanations and practice questions. CompSciTutoring.co.uk is not affiliated with or endorsed by an examination board. The marking guidance is indicative; always check the syllabus for your examination year.
Found an error? Email a correction.
Use the free examples first, then explore one-to-one tuition if guided practice would help.