Understanding the recursive solution for the Tower of Hanoi

Question

Can someone explain this program? I especially want to know how parameters are passed to the tower function and how recursion works.

Here is the code:

 #include<stdio.h> #include<conio.h> void main() { int n; clrscr(); printf("Enter the no. of disks"); scanf("%d",&n); tower(n,'S','D','T'); getch(); } tower(int n,char SOURCE,char DEST,char TEMP) { if(n>0) { tower(n-1,SOURCE,TEMP,DEST); printf("\nMove disk %d from %c to %c",n,SOURCE,DEST); tower(n-1,TEMP,DEST,SOURCE); } return; } 

Answer 1

This program illustrates the solution to the Tower of Hanoi problem.

So, you have heap 1 with n disks and 2 more empty stacks 2 and 3. You will need to move n disks from heap 1 to heap 3 (or from 1 to 2, it does not matter).

If you present n disks as (n-1 disks) and 1 disk, the problem becomes simple: move (n-1) to heap 2 and the last disk to dump 3.

So now you need to decide how to move (n-1) disks from heap 1 to heap 2, which means that you have the exact problem with n-1 disks. Repeat this process, and in the end you will reach such an extent that you only need to move 1 disk from heap 1 to heap 2.

Answer 2

Well, the best way to explain is to start by explaining how you do it in real life: To move N disks,

• First you move the N-1 discs to an intermediate position,
• Then you move the bottom drive to the destination,
• Finally, you move the N-1 discs from an intermediate position to their destination.

This code mimics. The only thing that needs to be understood is that the "roles" of the source, destination, and time value are different for the auxiliary towers.

• When I say "move N-1 from source to temp", it means source2 = source , dest2 = temp and, as a result, temp2 = dest .
• When you move the lower disk, everything does not change ( source3 = source , dest3 = dest , temp3 = temp
• When I say "move N-1 from temp to dest", it means source4 = temp , dest4 = dest and, as a result, temp4 = source .