15. Recursion & Backtracking

Recursion means solving a problem using a smaller copy of itself, plus a base case that stops the calls. Each call waits on the call stack until the smaller call returns.

Backtracking is recursion that builds an answer one choice at a time. The template is: choose, explore (recurse), un-choose. Subsets, permutations, combinations, N-Queens and Sudoku all use this same template. Only three things change between problems: the choices at each step, when a path is complete, and when to prune a dead branch early.