Monday, February 3, 2014

Tower of Hanoi

Tower of Hanoi is a classic problem to learn recursion. Here we see how recursion base conditions are generated, how parameters to the successive call to the same function are modified to give the desired output.

Problem at hand is : We have three pegs : A, B, C. Peg A contains N disks which are stack in such a way that any disk below is larger that then disk.
We need to move these N disks to Peg B in same condition mentioned above using the peg C.

First thing that comes into mind after reading or looking at the problem is : Move N-1 disks from peg A to peg C and then move the Nth disk to destination peg B. Now we have a problem left with N-1 disks which need to move from peg C to peg B using peg A as spare.
Easy enough ??

So we get the sight of recursion here?
First  : We need to do same process to N-1 disk which we did for N disks.
Second : Base case is when we are left with only one disk at source, we directly move that to destination.

Pseudo-code
Function Tower_Of_Hanoi:
If N==1 : Move disk from source to destination
else
Tower_Of_Hanoi (N-1, source, destination, helper)
Move disk from source to destination
Tower_Of_Hanoi (N-1, helper, destination, source)

Now we would see how stacks can be used to solve this problem. A rule of thumb is :  If a problem can be solved using recursion, it can also be solve using stack.
We need to map the recursion calls to stack.

Code
Code given here is of recursive implementation.

void tower_of_hanoi(int N, char source, char dest, char help){

        if(N>0){
                tower_of_hanoi(N-1, source, help, dest);
                printf("Moving disk from %c to %c\n", source, dest);
                tower_of_hanoi(N-1, help, dest, source);
        }

}

1 comment: