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.