Towers of Hanoi is a puzzle invented by the French mathematician Edouard Lucas in 1883. Quite likely, students have played or seen a version of Towers of Hanoi as it shows up in game stores and other venues.

Students should be able to solve the puzzle, especially when there are not too many disks, by simply trying things out. However, a systematic approach that can be used for any number of disks is not immediately obvious until a recursive approach is discovered. The recursion operates as follows (we use 5 disks as shown above):

- To move a tower of 5 disks from A to B, first move a tower of 4 disks from A to B
- Move the bottom peg (the largest one) from A to C
- Move the tower of 4 disks from B to C.

Of course, moving a tower of 4 disks from A to B involves moving a tower of 3 disks from A to C. This pattern continues until the final tower contains only 1 disk (the base case) in which case it involves simply moving one disk to the desired peg.

Give students time to think about how it works. Students often find it helpful to look at smaller examples before stating the solution in general terms.

**1 disk**

**2 disks**

- 1 disk solution to move top disk from A to B
- move remaining disk from A to C
- 1 disk solution to move 1 disk from B to C

**3 disks**

- 2 disk solution to move top 2 from A to B
- move disk from A to C
- 2 disk solution to move 2 from B to C

**4 disks **

- 3 disk solution to move top 3 from A to B
- move disk from A to C
- 3 disk solution to move 3 from B to C

We are now ready to describe the complete recursive algorithm for the Towers of Hanoi:

- Base Case: 1 disk
- Move 1 disk from peg A to peg C

- General Case: 2 or more disks
- Move top N-1 disks from peg A to peg B
- Move last disk from peg A to peg C
- Move top N-1 disks from peg B to peg C

There exist numerous links to explanations and online Towers of Hanoi games. Here are some we like: