Title: Recursively solve the Tower of Hanoi problem in C#

The example Recursively draw a binary tree in C# uses recursion to draw the branches of a tree. Good examples of recursion are hard to come by because the human brain normally thinks iteratively. For example, if you need to paint a fence, you probably think about starting at one end and working your way to the other. You probably don't think it terms of dividing the fence into two pieces and recursively painting each.

The Tower of Hanoi problem has a good, naturally recursive solution.

Consider the three orange pegs shown in the picture. The goal is to move the pile of green disks from the left peg to another (say the middle peg). You can only move one disk at a time and you can never place a big disk on a smaller disk.

Figuring out how to do this directly is tricky but there is a simple recursive solution. First recursively move every disk except the bottom one to the unused peg (in this case, the right peg). Now there is only one disk on the left peg and no disks on the middle peg so you can move the remaining disk there. Now recursively move the other disks from the right peg to the middle peg.

If that's too confusing, consider a smaller problem with only two disks. To move them from the left to middle peg, first move the top disk to the right peg. Then move the bottom disk to the middle peg. Finally move the top disk to the middle peg. Run the program a few times to see how it works for the larger problem. You can adjust the Delay constant in the code to make the program run slower or faster.

The program stores information about the disks in Stacks. A Stack provides a Push method to add something and a Pop method for removing the most recently added item. The program uses Stacks so it can only add and remove disks from the tops of the pegs. (No sneaking one out of the middle!) The OccupiedPegNum variable keeps track of the Stack that holds all of the disks (when they are not moving).

// Peg stacks. Each disk is represented by its width. Stack[] PegStack = new Stack[3]; // The peg that currently holds the disks. private int OccupiedPegNum = 0;

The following MoveDisks method is the key recursive routine.

// Move num_disks disks from peg from_peg to peg to_peg. private void MoveDisks(int from_peg, int to_peg, int other_peg, int num_disks) { // See if we have more than one disk to move. if (num_disks > 1) { // We have more than one disk to move. // Recursively move all but one disk to the other peg. MoveDisks(from_peg, other_peg, to_peg, num_disks - 1); } // Move the remaining disk. PegStack[to_peg].Push(PegStack[from_peg].Pop()); this.Refresh(); System.Threading.Thread.Sleep(Delay); if (num_disks > 1) { // Recursively move the other disks back where they belong. MoveDisks(other_peg, to_peg, from_peg, num_disks - 1); } }

MoveDisks takes parameters that tell it where to move the disks from and to, and which peg it can use as "temporary" storage. It also takes a parameter that tells it how many disks to move. To move the disks, the method recursively calls itself to move all but the bottom disk to the "temporary storage" peg, then moves the bottom disk, and then moves the other back from "temporary storage."

The rest of the program deal with moving the disks from one peg to another and pausing between the moves. It's not related to the recursive method, which is the main idea in this post, so I'm not going to describe it.

Download the example to experiment with it and to see additional details.