Puremass Home Puremass Mall Puremass Help LA Pig Judge Pig
Page: 1 2 3 4 of 4 Yellow Pig's Index

The Tower of Hanoi Puzzle

The Tower of Hanoi puzzle is often used as an introductory example for recursion in computer classes. A set of n discs are stacked on peg 1 ordered by size, with the largest at the bottom. You are to move these discs one by one to peg 3. You may use peg 2 for temporary placement. You may move only the topmost disc on a peg. You may not stack a disc on top of a smaller one.

Here is one way to program the recursive solution:

int move=0;
void towerrec(int n, int from, int temp, int to) {
  if (n == 1) 
    printf("%d: move disc %d from %d to %d\n", ++move, n, from, to);
  else {
    towerrec(n-1, from, to, temp);
    printf("%d: move disc %d from %d to %d\n", ++move, n, from, to);
    towerrec(n-1, temp, from, to);
In plain language, you first move the n-1 smaller discs to peg 2. Then you move the largest disc to peg 3. And then you move those same n-1 smaller discs again, this time to peg 3. Of course, you cannot move n-1 discs all at once, by the same reason that you could not move all n discs all at once, namely that the puzzle specifically prohibits moving more than one disc at a time. So you try to move n-2 discs first, etc. The recursion goes deeper and deeper until you reach the base case, where you actually move one disc.

Copyright © 2001 Pure Mass Communications