Lesson 08
Recursion & the Call Stack
A function that calls itself — and the invisible stack that makes it work.
01Why it matters & the intuition
Trees, graphs, divide-and-conquer sorts, backtracking and dynamic programming are all naturally recursive. If recursion feels like magic, the second half of this course will too.
Think of it like…
Russian nesting dolls: to count the dolls, open one and ask the doll inside to count the rest. The smallest doll — the one that doesn't open — is the base case. Every open doll waits on the stack until the one inside answers.
02See it move
Press play, then step through slowly. Change the input and predict the next frame before you click.
- on the call stack
- returned
- memo hit
03Key ideas
Base case
The input small enough to answer directly. Without it, recursion never stops and you get a stack overflow.
Recursive case
Shrink the problem and trust the function to solve the smaller version. fact(n) = n × fact(n − 1).
The call stack
Each call pushes a frame holding its local variables. Frames pop as calls return. Depth n means O(n) stack space.
Overlapping calls
Naive fib(n) recomputes fib(n − 2) many times, giving O(2ⁿ). Caching results (memoisation) drops it to O(n) — the seed of dynamic programming.
04Build it from scratch
A clean reference implementation. Read it line by line — then close it and write your own in the lab below.
function factorial(n: number): number {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case
}
// Naive: exponential because the same subproblems repeat.
function fibNaive(n: number): number {
if (n < 2) return n;
return fibNaive(n - 1) + fibNaive(n - 2);
}
// Memoised: each n is solved once.
function fibMemo(n: number, memo = new Map<number, number>()): number {
if (n < 2) return n;
const cached = memo.get(n);
if (cached !== undefined) return cached;
const value = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
memo.set(n, value);
return value;
}05Complexity
| Operation | Time | Space |
|---|---|---|
| factorial(n) | O(n) | O(n) stack |
| naive fib(n) | O(2ⁿ) | O(n) stack |
| memoised fib(n) | O(n) | O(n) |
| fast power(b, e) | O(log e) | O(log e) |
06Check your understanding
07Code lab
Write Python(or switch to JavaScript) and run it against real test cases. Python runs inside your browser — nothing is uploaded — and a C++ reference solution is under “Solution”.
Fast exponentiation
Write power(base, exp) for integer exp ≥ 0 using recursion in O(log exp) calls. Hint: b^e = (b^(e/2))² when e is even.