- They may only move one ring at a time.
- They may never move a larger ring on top of a smaller ring.

We can define a recursive solution to the puzzle as follows.

To move n rings from the source pole to the destination pole with a
spare pole:

- Move n-1 rings from the source pole to the spare pole using the destination as the spare.
- Move the single ring from the source pole to the destination pole.
- Move n-1 rings from the spare pole to the destination pole using the source pole as the spare.

This solution algorithm is naturally amenable to implementation in C. Assuming we only want to print out the moves of the individual rings, our function might look like:

void towers(int n, int src, int dest, int spare) { if(n > 0) { towers(n - 1, src, spare, dest); printf("Move a ring from tower %d to tower %d\n", src, dest); towers(n - 1, spare, dest, src); }

As with all the other recursive functions and algorithms we need a stopping condition for this. As we start with

```
n
```

, we continually decrease it toward 0.
When we hit 0, there are no rings to move and we need do nothing.
As with the algorithm, trace through this function for moving
4 rings from tower 1 to tower 3 with tower 2 as a spare.
By the way, moving 64 rings at the rate of one ring a second will take 350 million years. Maybe the legend isn't too far off after all.

Move on to the next part .