|
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.
|
