Reasoning: An Introduction to Logic, Sets, and Functions

Subsection 6.2.8 Solving the Towers of Hanoi – The Power of Recursion

Can you describe a procedure to solve the Towers of Hanoi puzzle? How many moves does your procedure take to solve the problem of 2 disks? 3 disks? 4 disks? 8 disks? 64 disks?

Here’s a procedure. Assume that, when you call it, you give it an integer n, the number of disks on the stack. Notice that it calls itself. So, for example, to move three disks, it first moves two out of the way, then it moves the one remaining (bottom) one. Then it moves the two disks onto the bottom one.

towersofHanoi(n: positive integer) =

1. If n = 1 then move the disk to the goal pole.

2. Else:

   1. Move the top n-1 disks to the pole that is neither the current one nor the goal.

   2. Move the bottom disk to the goal pole.

   3. Move the n-1 disks that were just set aside to the goal pole.

For 2 disks, it takes 3 moves. (Move one out of the way. Move the bottom one into place. Move the other one on top of it.) For 3 disks, it’s necessary to move 2 disks twice, plus the bottom one once. So 3+3+1=7 moves. For 4 disks, it’s necessary to move 3 disks twice, plus the bottom one once. So 7+7+1=15 moves. Can you see the pattern? Notice that 15 = 24 - 1. For 8 disks, it’s 28 – 1, which is 255. For 64 disks, it’s 264 – 1, which, at one move per second, would take 584,542,046,090 years, 228 days, 15 hours, 14 minutes and 45 seconds. That’s more than the number of years since the Big Bang.