Up: Recursion. Prev: Recurrences. Next: Closed-form solution.
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.
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.