= Tower of Hanoi
{c}
{title2=$T(n)=2^n-1$}
= Hanoi
{c}
{synonym}
The <Tower of Hanoi> has three pegs and $n$ differently sized discs. Start with all discs stacked largest below smallest on one peg; move one exposed disc at a time, never placing a larger disc on a smaller one, and transfer the stack to another peg.
To move the largest disc, the upper $n-1$ discs must first be collected on the third peg. After its move they must be transferred again. Hence the minimum satisfies $T(n)=2T(n-1)+1$, $T(0)=0$, giving $T(n)=2^n-1$. The recursive construction attains this <lower bound>. The problem shows how a short <recursive procedure> can require exponentially many executed moves.
Back to article page
