Up: Recursion. Prev: Recurrences. Next: Closed-form solution.

Will the world end soon?

To answer how long it will take our friendly monks to destroy the world, we write a recurrence (let's call it M(n)) for the number of moves MoveTower takes for an n-disk tower.

The base case - when n is 1 - is easy: The monks just move the single disk directly.

M(1) = 1 In the other cases, the monks follow our three-step procedure. First they move the (n-1)-disk tower to the spare peg; this takes M(n-1) moves. Then the monks move the nth disk, taking 1 move. And finally they move the (n-1)-disk tower again, this time on top of the nth disk, taking M(n-1) moves. This gives us our recurrence relation, M(n) = 2 M(n-1) + 1.

Since the monks are handling a 64-disk tower, all we need to do is to compute M(64), and that tells us how many moves they will have to make.

This would be more convenient if we had M(n) into a closed-form solution - that is, if we could write a formula for M(n) without using recursion. Do you see what it should be? (It may be helpful if you go ahead and compute the first few values, like M(2), M(3), and M(4).)

Next: Closed-form solution.