Explain what recursion is, and describe where it is a better fit than iteration.
Construct a simple recursive function in Python, and trace it by hand to find its return value.
Describe the role of the call stack, and evaluate recursion against iteration for memory and speed.
Recursion is a problem-solving technique where a function calls itself to solve a smaller version of the same problem.
The idea only works because the problem is self-similar: the answer for a big input can be written in terms of the answer for a slightly smaller input. Solving "sum a list of 10 numbers" becomes "the first number, plus the sum of the other 9" — the same problem, one step smaller.
Repeat that reduction and eventually you reach an input so small the answer is obvious and needs no further calls. That endpoint is what stops the process.
You're in a cinema queue and want to know your position. You can't see the front, so you ask the person ahead: "what number are you?"
They can't see either, so they ask the person ahead of them. The question travels forward, one person at a time.
The person at the very front answers "I'm 1" without asking anyone. That answer travels back, each person adding one. That's recursion: the same question passed down, and the answer built back up.
A condition where the function returns a value directly, without calling itself again.
It is the stopping condition. Without it, calls continue forever — in Python the interpreter eventually gives up and raises RecursionError. Every recursive function needs at least one.
The function calls itself with a smaller or simpler input, then uses the result.
The input must genuinely shrink each time, or the base case is never reached. "Smaller" means closer to the base case — a shorter list, a smaller number, one fewer character.
Ask: what is the smallest input I can answer instantly, with no further work? An empty list sums to 0. A single character reverses to itself. Write that answer down first — it becomes your stopping condition.
Trust the function to solve the smaller problem correctly, then express the full answer using that result. You do not need to imagine the whole chain of calls — one step is enough.
Confirm every recursive call moves strictly closer to the base case. If an argument can stay the same or grow, the function will never terminate.
def factorial(n): if n == 0: # base case return 1 # recursive case: return n * factorial(n - 1) print(factorial(5)) # → 120
Definition: n! = n × (n − 1)!
The function is defined in terms of itself on a smaller value. Each call peels off one multiplier and hands the rest downward.
Notice the order: the if comes first, so the stopping condition is checked before any further call is made.
5! = 5·4·3·2·1 = 120
factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * (3 * (2 * (1 * factorial(0))))
No multiplication happens on the way down. Each call just records what it still owes and waits.
= 4 * (3 * (2 * (1 * 1))) = 4 * (3 * (2 * 1)) = 4 * (3 * 2) = 4 * 6 = 24
Once factorial(0) returns 1, each waiting call finishes its multiplication in reverse order.
Every time a function is called, Python creates a stack frame — a small block of memory holding that call's own local variables and the line to return to when it finishes.
Frames are stacked: a new call pushes a frame on top, and a completed call pops its frame off. Only the top frame is running; everything beneath it is paused mid-line, waiting for a result.
So factorial(4) has five frames alive at its deepest point. That is the memory cost of recursion, and the reason very deep recursion overflows the stack while an equivalent loop never does.
Frames pop off top-down as each return value is passed back.
def mystery(n): if n <= 1: return 1 return n + mystery(n - 2) print(mystery(7))
Trace it on paper. Write down the value each call returns, in the order they resolve.
Then answer:
1. What is printed?
2. How many frames are on the stack at the deepest point?
3. What would happen with mystery(-3)?
| Call | n | Returns |
|---|---|---|
| mystery(7) | 7 | 7 + 9 = 16 |
| mystery(5) | 5 | 5 + 4 = 9 |
| mystery(3) | 3 | 3 + 1 = 4 |
| mystery(1) | 1 | 1 (base case) |
1. 16 is printed. The additions only happen on the way back up, once the base case has returned 1.
2. Four frames — mystery(7), (5), (3) and (1) are all alive at the deepest point, before any of them return.
3. It returns 1 immediately. The base case tests n <= 1, not n == 1, so negatives are caught too. Written as n == 1 it would recurse forever and raise RecursionError.
A programmer replaces a working iterative loop that sums a list of 100 000 numbers with a recursive function that produces the same result.
Explain two disadvantages of the recursive version compared with the iterative version.
Command term: EXPLAIN — give a detailed account including reasons or causes.
Each recursive call adds a stack frame holding its own local variables and return address [1], so memory use grows in proportion to the size of the list rather than staying constant as it does in a loop [1].
With 100 000 elements the recursion depth exceeds Python's maximum recursion limit [1], so the program raises a RecursionError and fails to produce a result at all, whereas the loop completes normally [1].
Also creditworthy: the overhead of creating and destroying a function call per element makes the recursive version slower than a simple loop, even where depth is within limits.
Three questions covering the three things this topic is examined on: stating the parts, constructing a function, and predicting output. Each is followed by a worked answer.
def reverse(s): return reverse(s[1:]) + s[0] print(reverse("stack"))
This function is meant to reverse a string, but it never produces an answer.
Identify the error.
Describe what the program does when run.
Outline the correction needed.
There is no base case — the function calls itself on every input with no condition that returns directly [1].
Each call shortens the string by one character, but once it is empty the function still recurses, so calls continue until Python's recursion limit is exceeded and a RecursionError is raised — nothing is printed [1].
Add a base case returning the string unchanged when its length is 1 or less, placed before the recursive call [1].
def reverse(s): if len(s) <= 1: # base case return s return reverse(s[1:]) + s[0] print(reverse("stack")) # → kcats
Construct a recursive Python function sum_list(numbers) that returns the total of all values in a list.
Your function must not use a loop and must not use Python's built-in sum().
Hint: what is the smallest list you can answer without any further work?
def sum_list(numbers): if numbers == []: # base case return 0 return numbers[0] + sum_list(numbers[1:])
Marks: base case for the empty list [1]; returns 0 there [1]; adds the first element to a recursive call [1]; recursive call passes the remaining slice so the list shrinks [1].
4 + sum_list([7, 2]) 4 + (7 + sum_list([2])) 4 + (7 + (2 + sum_list([]))) 4 + (7 + (2 + 0)) 4 + (7 + 2) 4 + 9 13
Four frames exist at the deepest point. The additions only resolve once the empty list returns 0.
def f(n): if n == 0: return "" return str(n) + f(n - 1) print(f(4))
def g(n): if n == 0: return "" return g(n - 1) + str(n) print(g(4))
State the output of each program, and explain why they differ despite identical base cases and identical recursive calls.
The digit is added before the recursive call, so each call contributes its digit on the way down. [1]
The recursive call is resolved first, so the deepest call's digit lands leftmost and each digit is appended on the way back up. [1]
Both functions make exactly the same calls in the same order. What differs is when the work happens: code placed before the recursive call executes while the stack is building, and code placed after it executes while the stack unwinds. Reversing that position reverses the output. [1]
A technique where a function calls itself to solve a smaller instance of the same problem.
The condition under which the function returns directly instead of calling itself, ending the recursion.
The part of the function that calls itself with a smaller input, moving toward the base case.
The memory structure holding one frame per active call, storing local variables and return points.
One block of memory on the call stack belonging to a single in-progress function call.
The Python exception raised when recursion depth exceeds the interpreter's limit — usually a missing or unreachable base case.
It continues with non-branching recursion on lists, strings and digits, branching recursion and the Fibonacci call tree, quicksort, binary tree traversal, fractals, Python's recursion limit, a full recursion-versus-iteration evaluation, and four more exam questions with mark schemes.
Close to 100 lessons like this one cover the whole 2027 syllabus, SL and HL — each with a matching printable handout, a unit revision booklet, and exam practice with worked answers.