Up: Recursion. Prev: How long it takes. Next: Exponentiation.
Let's figure out values of M for the first few numbers.
|M(2)=2M(1) + 1||=3|
|M(3)=2M(2) + 1||=7|
|M(4)=2M(3) + 1||=15|
|M(5)=2M(4) + 1||=31|
So the monks will move 264+1 (about 18.45x1018) disks. If they are really good and can move one disk a millisecond, then they'll have to work for 584.6 million years. It looks like we're safe.
Now we'll look at a very different, very practical problem: Exponentiation.