Beauty of Recursion.

Tower of Hanoi

Tower of Hanoi is a logic puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack inascendingorder of size on one rod, the smallest at the top, thus making a conical shape.(Wikipedia)

The objective of the puzzle is to move the entire stack to another rod, obeying the followingrules:

Only one disk may be moved at a time.

Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.

No disk may be placed on top of a smaller disk.

Logical analysis of the recursive solution (Please read it only when you finish the part 1 of the task below)

As in many mathematical puzzles, finding a solution is made easier by solving a slightly more general problem: how to move a tower of h (h=height) disks from a starting pegA (f=from) onto a destination pegC (t=to),B being the remaining third peg and assumingtf. If a solution is known moving from pegA to pegC, then, by renaming the pegs, the same solution can be used for every other choice of starting and destination peg. If there is only one disk (or even none at all), the problem is trivial. If h=1, then simply move the disk from pegA to pegC. If h>1, then somewhere along the sequence of moves, the largest disk must be moved from pegA to another peg, preferably to pegC. The only situation that allows this move is when all smaller h-1 disks are on pegB. Hence, first all h-1 smaller disks must go fromA toB. Subsequently move the largest disk and finally move the h-1 smaller disks from pegB to pegC. The presence of the largest disk does not impede any move of the h-1 smaller disks and can temporarily be ignored. Now the problem is reduced to moving h-1 disks from one peg to another one, first fromA toB and subsequently fromB toC, but the same method can be used both times by renaming the pegs. The same strategy can be used to reduce the h-1 problem to h-2, h-3, and so on until only one disk is left. This is called recursion. This algorithm can be schematized as follows. Identify the disks in order of increasing size by the natural numbers from 0 up to but not including h. Hence disk 0 is the smallest one and disk h-1 the largest one.The following is a method for moving a tower of h disks from a pegfrom onto a pegto, withtemp being the remaining third peg:

Step 1: If h>0 then first use this method to move the h-1 smaller disks from pegfrom to pegtemp.

Step 2: Now the largest disk, i.e. disk h-1 can be moved from pegfrom to pegto.

System.out.print(from+"->"+to+" ");

Step 3: If h>0 then again use this method to move the h-1 smaller disks from pegtemp to pegto.

Task.

Part 1. It is a very important part because it is like a warm up for your brain. The more you practice from a simple solution to more and more complicated solutions, the more development and activation you have in the abstract thinking part of your brain.

Play the puzzle for h=3,4,5 on the website.http://www.mathsisfun.com/games/towerofhanoi.html

Try to find the solution for h=2,3,4,5. When you figure out the solution for 3, try to use the solution for 2 to get the solution for 3. Then try to do the solution for 4 by using the algorithm for 3. Then try to find the solution for 5 by using the algorithm for 4.

Part 2. Programming.

Pegs:

A B C

You need to ask user for the number of rings h, then you should have a program with recursions that prints a solution: how to move h rings from A to C by using B. (see the Hanoi Tower rules on the beginning this handout)

Have a java application that shows the solution in the following way:

h=3

A->C A->B C->B A->C B->A B->C A->C >

h=4

A->B A->C B->C A->B C->A C->B A->B A->C B->C B->A C->A B->C A->B A->C B->C >

Method call:

/* Tower of hanoi

** Pre: int h, number of rings, String start peg, Temp peg, final peg

tower(h,"A","B","C");

public static void tower(int n, String start, String temp, String final){