Recursion is solving a problem by solving a smaller copy of the same problem, then doing one small step with the result. Every recursive function has the same two parts, and every recursion question is checking that you know them.
The two parts
- Base case — an input small enough to answer without recursing. Without it the function never stops.
- Recursive case — do a little work, and call the function on an input that is closer to the base case.
def factorial(n):
if n == 0: # base case
return 1
return n * factorial(n - 1) # recursive case: smaller nfactorial(4) = 4 × factorial(3) = 4 × 3 × factorial(2) = 4 × 3 × 2 × factorial(1) = 4 × 3 × 2 × 1 × factorial(0) = 24.
The call stack — what actually happens
Each call waits for the inner one to return. Picture a stack of plates:
factorial(4) waits for factorial(3)
factorial(3) waits for factorial(2)
factorial(2) waits for factorial(1)
factorial(1) waits for factorial(0)
factorial(0) → returns 1
factorial(1) → 1 × 1 = 1
factorial(2) → 2 × 1 = 2
factorial(3) → 3 × 2 = 6
factorial(4) → 4 × 6 = 24Going down is the winding; coming up is the unwinding. Exam trace questions want both halves written out like this.
Example 2 — Fibonacci, and why naive recursion is slow
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)Correct, but fib(30) makes over a million calls because it recomputes the same values. Remember the results (memoisation) and it becomes linear:
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
return n if n <= 1 else fib(n - 1) + fib(n - 2)Example 3 — sum of digits
def digit_sum(n):
if n < 10:
return n
return n % 10 + digit_sum(n // 10)digit_sum(472) = 2 + digit_sum(47) = 2 + 7 + digit_sum(4) = 2 + 7 + 4 = 13.
Example 4 — binary search
def bsearch(a, x, lo, hi):
if lo > hi:
return -1 # base case: not found
mid = (lo + hi) // 2
if a[mid] == x:
return mid # base case: found
if x < a[mid]:
return bsearch(a, x, lo, mid - 1)
return bsearch(a, x, mid + 1, hi)Each call halves the range, so the depth is about log₂ n — for a million elements, about 20 calls.
Example 5 — Tower of Hanoi
Move n discs from A to C using B: move n − 1 discs A → B, move the biggest A → C, move n − 1 discs B → C.
def hanoi(n, src, dst, via):
if n == 0:
return
hanoi(n - 1, src, via, dst)
print(f"disc {n}: {src} -> {dst}")
hanoi(n - 1, via, dst, src)Number of moves: 2ⁿ − 1. Three discs take 7 moves; this is the standard "how many moves" question.
Recursion vs iteration
| Recursion | Iteration | |
|---|---|---|
| Written as | Function calling itself | Loop |
| Memory | A stack frame per call | Constant |
| Speed | Slower (call overhead) | Faster |
| Best for | Trees, divide and conquer, backtracking | Simple repetition, counting |
| Risk | Stack overflow if too deep | Infinite loop if the condition is wrong |
Any recursion can be rewritten as a loop with an explicit stack; the reverse is also true. Choose the one that reads clearly.
Where students go wrong
- No base case, or one that is never reached — e.g.
factorial(n - 2)from an odd n skips 0 and runs into negatives. - Forgetting to
returnthe recursive call.factorial(n - 1)on its own computes the value and throws it away. - Changing the wrong thing. The recursive call must move toward the base case; recursing on the same n is an infinite loop.
- Tracing from the top only. Write the unwinding too — that is where the answer is assembled.