Sign in to watch this lesson
Algorithms - Recursion, Backtracking and Combinatorics · 5:25
Recursion Trees and the Backtracking Template
We draw every call of the Tower of Hanoi at once: seven nodes for three disks, each making one move, and the moves come out in left-to-right order, so a recursive function costs its node count times the work per node (2^n - 1 for Hanoi, about b^d in general). The same tree then becomes a decision tree for trading schedules that never trade two minutes in a row, walked with the choose, explore, un-choose template on one shared vector, and pruning cuts 20 minutes from 2,097,151 nodes to 46,366. Finally the classic traps: the missing pop (2 schedules instead of 5), copying the path into every call (about 10x slower here), stack depth and stale global counters.
You will learn
- Draw the recursion tree of a recursive function and estimate its cost as nodes times work per node (2^n - 1 for Hanoi, about b^d for branching b and depth d).
- Write a backtracking search with the choose, explore, un-choose template on one shared mutable state.
- Add pruning that rejects a choice before descending, and explain why it helps in practice without changing the worst case.
- Recognise the common backtracking bugs: a missing un-choose, state passed by value, deep linear recursion and global counters that are never reset.