Algorithms from zero
Recursion and backtracking: build a pruning solver
Reading about pruning is not the same as watching it shrink a search. Build one backtracking solver, instrument it to count every recursive call, then add pruning and watch the recursion tree collapse, with the call counts to prove it.
Turn the unit’s mental model into working code: implement the choose-explore-undo template for a real constraint problem, instrument the recursion tree, add pruning, and verify the speedup with measured before/after node counts rather than intuition.
Build a backtracking solver for a constraint problem (N-Queens, or a Sudoku/subset-sum/word-search variant), prove it finds all valid solutions, then add pruning and measure the reduction in recursive calls it produces.
- A before/after table: input size, recursive-call count with no pruning, recursive-call count with pruning, and solutions found, all measured from the counter, not estimated.
- Pruning reduces the recursive-call count substantially (for N-Queens n = 8, brute force over placements is billions; the pruned solver visits only thousands of nodes) while the solution set is byte-for-byte identical between versions.
- Each recorded solution is a real copy: mutating one solution after the run does not change any other, demonstrating you snapshotted current rather than storing a reference.
- A short write-up naming the base case, the choice, the constraint, and the prune condition, plus one sentence on why depth stays O(n) on the call stack even as the node count changes.
- Add a depth/visualisation trace that prints the recursion tree (indented by depth) for a tiny instance so you can see choose-explore-undo and the pruned branches directly.
- Convert the recursive solver to an explicit-stack iterative version and confirm it produces the same solutions, then reason about which one you would ship if the input depth were untrusted.
- Add memoisation to an overlapping-subproblem variant (e.g. count subset-sum ways) and report how the recursive-call count drops from exponential toward polynomial.
- Generalise the solver to take the choice generator, validity check, and completion test as parameters, so the same engine solves all three of your candidate problems.
This is the loop you run on any search problem: name the base case, the choices, and the constraint; write the choose-explore-undo skeleton and record copies; measure the recursion tree with a call counter; then add a prune that checks the constraint before recursing and watch the node count collapse while the answer set stays identical. Doing it once on a toy solver makes the pattern, and the reason pruning matters, permanent.