Tower of Hanoi

Move n disks from peg 1 to peg 3, one disk at a time, never placing a larger disk on a smaller one. The recursive insight:

1. move the top n − 1 disks from source to spare
2. move the biggest disk from source to target
3. move the n − 1 disks from spare to target

def hanoi(n, src, dst, via):
    if n == 0: return
    hanoi(n - 1, src, via, dst)
    moves.append([src, dst])
    hanoi(n - 1, via, dst, src)

That makes 2ⁿ − 1 moves, and it's provably optimal. Trust the recursion: assume the smaller call works, and only reason about one level.