The Towers of Hanoi

I think this is the most popular recursive algorithm! I find it to be one of the best examples to show recursion power!
The idea is that there are 3 towers, I gonna name them "ini", "temp" and "end" and 'n' disks.
The initial state is defined as all the disks in the "ini" tower.
Each disk has a unique diameter and the goal is to move all the disks from the "ini" to "end" using "temp", if needed.
Some rules are to be honored:
This is an animation for 4 disks:
hanoi animation, 4 disks

The recursive solution

At first this game seems very difficult to solve, specially for a big number of disks...
But it has a strong recursive nature. If somehow we could get the problem solved for (n-1) disks shown as follows: hanoi step 1 Then we only need to move the n-disk from "ini" to "end" to get the configuration: hanoi step 2 And now again if somehow we could move (n-1) from "temp" to "end" then the game is solved! hanoi step 3 So to sum up we've moved: Of course that step 1 and 3 don't follow the rule that only one disk must be moved at the time. So we need to think of a way to do this, moving only one disk each time. It's not very hard to see that this is very much like the original problem but with two changes: we have one disk less and the origin and destination of the disks have changed! These changes don't affect the shape of the problem! We can completely forget about the n-disk and since this is the biggest then we don't have to worry about breaking the rule that no bigger disk can be above it! So we can solve this by calling this algorithm recursively for step 1 and 3.

Therefore our new algorithm will look like: By this point you would have probably remembered that we need a base case, this is, a situation where we stop the recursion! For one disk the solution is trivial, so we can go with it or we can use the zero disk problem which is easer since there is nothing to be done!
Finally our code (in Java) would be:
/**
 *
 * @author Kriche
 */
public class Hanoi {

    private static final int DISKS = 4;
    private static final String INI_TOWER_NAME = "ini";
    private static final String TEMP_TOWER_NAME = "temp";
    private static final String END_TOWER_NAME = "end";

    /**
     * 
     * @param args
     */
    public static void main(String[] args) {
        System.out.println("Hanoi for " + DISKS + " disks!");
        hanoi(DISKS, INI_TOWER_NAME, TEMP_TOWER_NAME, END_TOWER_NAME);
    }

    /**
     * 
     * @param disk
     * @param ini
     * @param temp
     * @param end
     */
    private static void hanoi(int disks, String ini, String temp, String end) {

        // recursive implementation

        //Base case check
        if (disks > 0) {

            hanoi(disks - 1, ini, end, temp);

            // Our contribution to get closer to the base case:
            // Just for demo, use StringBuffer or StringBuilder in actual programs!
            System.out.println("\tMove disk: " + disks + " from " + ini + " to " + end + ".");

            hanoi(disks - 1, temp, ini, end);

        }

    }

}
Running this program will produce this output:
Hanoi for 4 disks!
	Move disk: 1 from ini to temp.
	Move disk: 2 from ini to end.
	Move disk: 1 from temp to end.
	Move disk: 3 from ini to temp.
	Move disk: 1 from end to ini.
	Move disk: 2 from end to temp.
	Move disk: 1 from ini to temp.
	Move disk: 4 from ini to end.
	Move disk: 1 from temp to end.
	Move disk: 2 from temp to ini.
	Move disk: 1 from end to ini.
	Move disk: 3 from temp to end.
	Move disk: 1 from ini to temp.
	Move disk: 2 from ini to end.
	Move disk: 1 from temp to end.

We've done a lot of progress! The problem is solved but there is much more to see!
Later in "Recursion Removal" we will see a nonrecursive solution to this fascinating problem!!