Thinking Recursively with Java

Chapter 5. The Tower of Hanoi

"Firstly, I would like to move this pile from here to there," he explained, pointing to an enormous mound of fine sand; "but I'm afraid that all I have is this tiny tweezers." And he gave them to Milo, who immediately began transporting one grain at a time.

—Norton Juster, The Phantom Tollbooth, 1961

Toward the end of the nineteenth century, a new puzzle appeared in Europe and quickly became quite popular on the continent. In part, its success can be attributed to the legend that accompanied the puzzle, which was recorded in La Nature by Henri de Parville (as translated by the mathematical historian W.W.R. Ball).

In the great temple at Benares beneath the dome which marks the center of the world, rests a brass plate in which are fixed three diamond needles, each a cubit high and as thick as the body of a bee. On one of these needles, at the creation, God placed sixty-four disks of pure gold, the largest disk resting on the brass plate and the others getting smaller and smaller up to the top one. This is the Tower of Brahma. Day and night unceasingly, the priests transfer the disks from one diamond needle to another according to the fixed and immutable laws of Brahma, which require that the priest on duty must not move more than one disk at a time and that he must place this disk on a needle so that there is no smaller disk below it. When all the sixty-four disks shall have been thus transferred from the needle on which at the creation God placed them ...