The question this module answers: how do you explore every possibility without writing a loop for each one?
Subsets, orderings, placements, configurations: the number of nested choices isn't known in advance, so you can't
write that many for loops. Recursion writes one level of choice and lets the call stack repeat it.
Backtracking adds two habits: undo each choice when you return, and stop exploring a branch as soon as it can't
succeed.
ML context.
- Search over configurations: hyperparameter grids with constraints (lesson 8.10), feature subsets under a cost budget (lesson 8.3), valid architectures from a set of blocks.
- Tree-shaped computation: parsing nested configs and JSON, walking a model's module tree (
model.named_modules()is a recursive walk), decision trees. - Constraint solving: scheduling jobs onto GPUs, generating valid structured outputs.
1. Recursion and the recursion tree
A recursive function needs a base case (answer directly) and a recursive case (reduce to smaller inputs). Its cost is easiest to see by drawing the recursion tree: one node per call, children for the calls it makes.
Total work = number of nodes × work per node.