Module 12
Recursion
Solve a problem using a smaller copy of itself: pick a base case, trust the recursive call, and learn what it costs in time and stack.
Recursion is a way of thinking before it's a coding technique: if you can describe the answer for size n in terms of the answer for a smaller size, the code almost writes itself. Trees, backtracking, divide and conquer and dynamic programming all build on it.
This module covers the leap of faith (trusting the smaller call), what the call stack really does, how to estimate cost with a recursion tree, and when to turn recursion into a loop because Java has no tail-call optimisation.
Best after: Java for DSA
Part 1
Learn the ideas
- 12.1Thinking RecursivelyEvery recursive function has a base case that stops, and a recursive case that shrinks the problem and trusts the smaller call to be correct.14 min
- 12.2What the Call Stack DoesEach call gets a frame with its own variables; frames stack up until the base case, then unwind in reverse, combining results.12 min
- 12.3Recursion Trees and CostDraw the calls as a tree: the number of nodes times the work per node is the time; the tree's height is the stack space.14 min
- 12.4From Recursion to LoopsJava doesn't optimise tail calls, so deep linear recursion should become a loop or use an explicit stack.10 min
Part 2
Solve the problems
In order of difficulty. Each one shows the pattern it teaches.
The same problem in three costs: exponential recursion, memoised recursion, and an O(1)-space loop.
Fast exponentiation: xⁿ = (x^(n/2))², so the recursion depth is log n, not n.
A loop rewritten as recursion: swap the ends, then recurse on the inside. Shows how depth becomes stack space.
The classic leap of faith: to move n discs, trust that you can move n − 1 discs, twice.
Recurse on the structure instead of building it: each symbol depends only on its parent in the previous row.