def solve(problem): return solve(smaller_problem)
Explain the fundamental concept of recursion in your own words.
Identify the base case and recursive case in any recursive function.
Construct and trace simple recursive algorithms in Python.
Describe recursive algorithms such as quicksort and tree traversal.
Evaluate the advantages and limitations of recursion — memory and complexity.
Choose when recursion is the right tool for a problem.
The idea, the two parts, the call stack.
Building and tracing recursion in Python.
Quicksort, trees, fractals, the recursion limit.
Trade-offs, pitfalls and exam practice.
The idea · the two parts · the call stack
A recursive function is one that calls itself to solve a smaller instance of the same problem.
Each call breaks the problem into a slightly smaller one, until it becomes so small the answer is obvious — and the calls resolve back up.
// analogy
A set of Russian dolls — open one and find a smaller one inside, and again, until you reach the smallest solid doll that opens no further.
The simplest input, where the answer is known directly — no further calls needed. This is what ends the recursion.
if n == 0:
return 1
The function calls itself on a smaller input, making progress toward the base case each time.
return n * factorial(n - 1)
⚠ No base case (or one you never reach) → infinite recursion → program crash.
The smallest input you can answer directly, with no further call.
Express the answer using the result of the same function on a smaller problem.
Make sure every call moves closer to the base case so it will 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.
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))))
factorial(0) hits the base case → returns 1.
= 4 * (3 * (2 * (1 * 1))) = 4 * (3 * (2 * 1)) = 4 * (3 * 2) = 4 * 6 = 24
Nothing is multiplied until the base case is reached.
Each call adds a stack frame holding its own n and its return point.
Calling pushes a frame on top.
Returning pops it off.
The stack reaches its deepest at factorial(0), then empties as values return upward.
Step through factorial(n) and watch the stack grow one frame per call, stop at the base case, then collapse as each frame receives the answer below it and returns.
A function calls itself directly.
def f(n): return f(n - 1)
A calls B, and B calls A back.
def is_even(n): return n == 0 or is_odd(n-1) def is_odd(n): return n != 0 and is_even(n-1)
Constructing recursion in Python — B2.4.5
def countdown(n): if n == 0: print("Blast off!") else: print(n) countdown(n - 1) countdown(3)
3 2 1 Blast off!
One recursive call per step → non-branching. The base case (n = 0) stops it.
Each variant breaks termination in a different way. Run them and see that having a base case is not enough — the argument has to move towards it, in steps that actually land on it.
def total(nums): if nums == []: # base case return 0 return nums[0] + total(nums[1:]) total([4, 2, 7]) # → 13
sum(list) = first + sum(rest)
4 + total([2, 7])
4 + (2 + total([7]))
4 + (2 + (7 + total([])))
4 + (2 + (7 + 0)) = 13
def digit_sum(n): if n < 10: # base case return n return n % 10 + digit_sum(n // 10) digit_sum(1234) # → 10
n % 10 → last digitn // 10 → drops last digit
4 + digit_sum(123)
4 + 3 + digit_sum(12)
4 + 3 + 2 + digit_sum(1)
4 + 3 + 2 + 1 = 10
def reverse(s): if s == "": # base case return "" return reverse(s[1:]) + s[0] reverse("cat") # → "tac"
reverse(s) = reverse(rest) + first
reverse("at") + "c"
(reverse("t") + "a") + "c"
((reverse("") + "t") + "a") + "c"
"t" + "a" + "c" = "tac"
def power(b, e): if e == 0: # base case return 1 return b * power(b, e - 1) power(2, 4) # → 16
be = b × be−1
2 * power(2, 3)
2 * 2 * power(2, 2)
2 * 2 * 2 * power(2, 1)
2 * 2 * 2 * 2 * 1 = 16
def fact(n): if n == 0: return 1 return n * fact(n-1)
def fact(n): r = 1 for i in range(1, n+1): r *= i return r
def mystery(n): if n == 0: return 0 return n + mystery(n - 1) mystery(3) # = ?
Trace it on paper. Write down the value returned at each level before checking.
Hint: it computes 1 + 2 + … + n
def fib(n): if n <= 1: # base cases return n return fib(n-1) + fib(n-2) fib(6) # → 8
Each term is the sum of the two before it:
0, 1, 1, 2, 3, 5, 8, 13 …
Two self-calls make this branching recursion — a tree of calls, not a line.
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2)fib(1).. fib(1)fib(0)
The same sub-problems are recomputed many times:
fib(2) is computed 3×, fib(1) 5×.
Work grows exponentially — fib(50) needs billions of calls. Redundant work is a real risk of naive recursion.
Each bar counts how many separate times naive Fibonacci computes that value from scratch. Raise n and watch the total; the amber bars are pure wasted work that memoisation removes.
Quicksort · trees · fractals · the recursion limit
Self-similar images — a shape drawn from smaller copies of itself, e.g. the Koch snowflake or Sierpiński triangle.
Each subtree is itself a tree, so traversal (in-, pre-, post-order) is written recursively on left and right children.
Divide-and-conquer sorts — quicksort and merge sort — split the data and sort each part recursively.
Common thread → problems that break into smaller, self-similar sub-problems.
Pick one element from the list as the reference point.
Split the rest into items < pivot and items ≥ pivot.
Sort each half recursively, then concatenate: left + pivot + right.
Base case: a list of 0 or 1 element is already sorted — return it unchanged.
def quicksort(arr): if len(arr) <= 1: # base case return arr pivot = arr[0] less = [x for x in arr[1:] if x < pivot] more = [x for x in arr[1:] if x >= pivot] return quicksort(less) + [pivot] + quicksort(more)
pivot=5
less=[3,1] more=[8]
→ qs([3,1]) + [5] + qs([8])
→ [1,3] + [5] + [8]
→ [1, 3, 5, 8]
def inorder(node): if node is None: # base case return inorder(node.left) print(node.value) inorder(node.right)
Each subtree is itself a tree, so the same function handles the whole structure.
In-order → left, node, right. On a binary search tree this prints values in sorted order.
base case = an empty (None) node
import turtle def koch(t, length, depth): if depth == 0: # base case t.forward(length) else: for angle in [60, -120, 60, 0]: koch(t, length/3, depth-1) t.left(angle)
A self-similar shape: each segment is replaced by four smaller copies of the same curve.
Increasing depth adds finer detail — the same rule applied at smaller and smaller scale.
import sys sys.getrecursionlimit() # → 1000 sys.setrecursionlimit(3000) # too deep → RecursionError: # maximum recursion depth exceeded
Each call needs a stack frame, so Python caps the depth (~1000) to avoid exhausting memory.
Exceed it and you get a RecursionError, not a crash. Raising the limit is risky — deep problems are usually better solved with iteration.
Trade-offs · pitfalls · key terms · exam practice
Cleaner, shorter code for problems that are naturally recursive.
Mirrors the definition — code closely matches the maths or data structure.
Less manual bookkeeping — the call stack tracks state a loop would manage by hand.
Natural fit for trees, graphs and divide-and-conquer algorithms.
Each call keeps a stack frame alive → O(depth) extra memory versus O(1) for a loop.
Each call has setup/return cost, so recursion is usually slower than the equivalent iteration.
Too many calls exceed Python's limit (~1000) → RecursionError and a crash.
Naive recursion (e.g. Fibonacci) recomputes the same sub-problems many times.
No base case — the function never stops calling itself.
No progress — the call doesn't shrink the input toward the base case.
Fix: confirm the base case is reachable and each call makes the problem smaller.
def countdown(n): print(n) countdown(n - 1) # no base case! # … -1, -2, -3 … RecursionError
Base case — the input answered directly, ending the recursion.
Recursive case — the part that calls the function on a smaller input.
Call stack — the store of active calls waiting to finish.
Stack frame — one call's local variables and return point.
Infinite recursion — no reachable base case; never stops.
Stack overflow — too many calls exceed the depth limit.
Divide & conquer — split a problem, solve parts, combine.
Tail recursion — recursive call is the last step (Python doesn't optimise it).
Write a recursive function power(b, e) that returns be.
Write a recursive function that counts the items in a list.
Explain what happens if a recursive function has no base case.
Give one problem well suited to recursion and one better solved with a loop. Justify each.
(a) State the two parts every recursive algorithm must contain.
[2](b) Construct a recursive function in Python to calculate the factorial of a non-negative integer n.
[4](c) Outline one limitation of using recursion instead of iteration for this task.
[2]Watch the command terms: State · Construct · Outline — each expects a different depth of answer.
01 Recursion = a function calling itself on a smaller sub-problem.
02 Always needs a base case and a recursive case that makes progress.
03 Ideal for self-similar problems: trees, fractals, quicksort.
04 Costs memory via the call stack — can be slow or overflow.
05 You must be able to construct and trace simple recursion by hand.
B2.4.4 · B2.4.5 | IB Computer Science HL
Unlimited AI-generated questions · instant feedback · a live Python runner
Nothing in this deck was cut down for the sample. Every lesson across Themes A and B is built to the same depth — syllabus-mapped objectives, worked Python, interactive visualisers, tracing practice and exam-style questions with mark schemes.