The world of computer science offers many challenging problems in designing algorithms to programme
a computer.
Sophisticated algorithms now exist for tasks such as, cryptography, data compression, and image processing.
But before our students at Warwick can address such interesting applications they would first have to
master the basic programming problems and methods.
In this demonstration we study one such problem and a standard technique to solve it.

### The towers of Hanoi

Suppose I have a number of rings on a pole and I want to move them all to another pole one by one.
The constraint is that no larger ring may at any time rest on a smaller ring.
When my initial pile has one, two, or three rings you can probably work out hot to solve the problem
in each such case.
But clearly the more rings there are the harder it gets to solve the problem in each case.
It if you don't believe it why not try the Javalovers demo on the web at
http://www.javalovers.com/hanoi.htm.
So what if I want to write a program which will work for any pile of rings however large.
We need an algorithm which will work for an arbitrarily large pile of rings.
### Divide and conquer your problems!

Not only is this good advice for solving lots of our everyday problems it is also one of the
most basic tools for solving problems on a computer.
Break your problem into its subproblems, solve each sub problem, then combine those solutions to
solve the original problem.
In applying this method to the towers of Hanoi we break the problem of moving *n* rings
(in our example here it is *5*) into two sub problems, each of how to move *n-1* rings.
This is the technique known as *recursion* where a problem of 'size' *n* is broken down
into problem(s) of size some number less than *n* (more often than not *n-1*).
Problems get repeatedly broken down into smaller problems until we reach the so called 'base case'
where (typically *n=1*) we can solve the problem by trivial or other means.
The Hanoi problem for one ring is clearly trivial.
Here now is the recrusive solution to the Hanoi problem for *5* rings.

### How do we code up this recursive algorithm in a programming language ?

There is a bit more to think about when defining our '*n*-problem' for the Hanoi towers than
just saying we need to move *n* rings, we also need to know from which pole and to which pole
the rings are moved.
Let us name the poles *1*, *2*, and *3*.
Then the problem is to recursively define the sequence of actions to move *n* rings
from any pole *a* to any other pole *b*.

**if** *n=1* **then** move one ring from pole
*a* to pole *b*

**else** move *n-1* rings from pole
*a* to pole *6-a-b*

move one ring from pole *a* to pole
*b*

move *n-1* rings from pole
*6-a-b* to pole *b*

This algorithm is expressed here in English, but
first year students here at Warwick would be asked to write it in the *Java* programming language.
### How does the computer execute this program ?

This is an interesting question, as how can the computer be half way through solving a problem such
as, *move 5 rings from pole 1 to pole 3* in order to start the new smaller problem,
*move 4 rings from pole 2 to pole 3* ?
Would it not have to stop working on one problem in order to start working on another ?
The answer is that the computer suspends working on the larger problem while it solves the smaller one.
For any *n* there are *2*^{n-1}-1 problems to start
and then suspend in
solving the Hanoi problem for *n* rings. Thus for the *5* ring problem we need
to keep track of *15* suspended problems.
This is why the Hanoi problem is too hard for most humans to solve when *n* exceeds *4*;
human memory is just too unreliable compared with that of a computer.
In this modern age we no longer have to know how to move the rings, but rather how to instruct a
machine to do it for us, and that is the wonderous challenge of programming!