A level-readyAll subjects · Computer Science · WCP02 Practical Programming and Problem-solving
Recursion
Edexcel IAL Computer Science · WCP02 Practical Programming and Problem-solving
A recursive subprogram calls itself on a smaller version of the problem until it reaches a case it can answer directly.
Base case and recursive case (spec 10.4.1)
Every recursive subprogram needs:
- a base case, answered without recursion, which stops the calls;
- a recursive case, which calls the subprogram with a smaller problem that moves towards the base case.
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
print(factorial(5))Output:
120How the calls unwind
Each call waits for the one it made. factorial(4) = 4 x factorial(3) = 4 x 3 x factorial(2) = 4 x 3 x 2 x factorial(1) = 4 x 3 x 2 x 1. The results are then multiplied as the calls return, last call first, using the call stack.
def countdown(n):
if n == 0:
print("Go")
else:
print(n)
countdown(n - 1)
print("back in", n)
countdown(2)Output:
2
1
Go
back in 1
back in 2More examples and risks
Recursion suits problems that contain smaller copies of themselves: binary search, summing digits, traversing nested data.
def sum_digits(n):
if n < 10:
return n
return n % 10 + sum_digits(n // 10)
def power(base, exp):
if exp == 0:
return 1
return base * power(base, exp - 1)
print(sum_digits(4096), power(3, 4))Output:
19 81Without a reachable base case the calls never stop: Python raises RecursionError when the call stack limit is reached. Each call also uses memory, so an iterative loop can be more efficient.
Worked example
Trace sum_digits(507).
- 507 is not < 10: 7 + sum_digits(50)
- 50 is not < 10: 0 + sum_digits(5)
- 5 < 10: base case returns 5
- Unwind: 0 + 5 = 5, then 7 + 5 = 12
Answer: 12
Check yourself
- What is displayed when this code runs?
```python
def f(n):
if n == 0:
return 1
return n * f(n - 1)
print(f(4))
```
Show answer
24. 4 x 3 x 2 x 1 x 1 = 24.
- What is displayed when this code runs?
```python
def total(n):
if n == 1:
return 1
return n + total(n - 1)
print(total(6))
```
Show answer
21. 6 + 5 + 4 + 3 + 2 + 1 = 21.
- What is displayed when this code runs?
```python
def show(n):
if n > 0:
show(n - 1)
print(n, end=" ")
show(3)
```
Show answer
1 2 3 . The recursive call comes before print, so the numbers print as the calls unwind: 1 2 3.
- How many times is fib called in total by fib(4)?
```python
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
```
Show answer
9. fib(4) calls fib(3) and fib(2), which call more: 9 calls in total, including the first.
- What is displayed when this code runs?
```python
def rev(s):
if len(s) <= 1:
return s
return rev(s[1:]) + s[0]
print(rev("code"))
```
Show answer
edoc. Each call moves the first character to the end of the reversed rest: edoc.
- Which exception is raised when this code runs?
```python
def forever(n):
return forever(n + 1)
forever(1)
```
- IndexError
- ZeroDivisionError
- ValueError
- RecursionError
Show answer
RecursionError. There is no base case, so the calls go on until Python's limit and it raises RecursionError.
- What is the purpose of the base case in a recursive subprogram?
- To make the first call
- To stop the recursion by giving an answer without another call
- To speed up every call
- To store the result in a global variable
Show answer
To stop the recursion by giving an answer without another call. Without a base case the subprogram would call itself for ever.
Sources
- Pearson Edexcel International Advanced Subsidiary/Advanced Level in Computer Science specification (XCP01/YCP01), first teaching 2026
- Pearson IAL Computer Science Unit 2 Programming Language Subset (PLS), Python 3
- Pearson IAL Computer Science IAS sample assessment materials (Unit 2 paper and mark scheme)
Last updated 8 November 2026. Spotted a mistake? Tell us.