Understanding recursive solution to Towers of Hanoi

Question

Can anybody please explain this program? I especially want to know how the parameters are passed to the function tower and how the 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 for Tower of Hanoi problem.

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

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

So now you need to work out how to move (n-1) disks from pile 1 to pile 2, which means you have the exact problem with n-1 disks. Repeat the process and eventually you'll get to the point that you only need to move 1 disk from pile 1 to pile 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 N-1 disks to the intermediate position,
• Then you move the bottom disk to the destination,
• Finally you move the N-1 disks from the intermediate position to the destination.

The code mimics that. The only thing to understand is that the "roles" of source, destination and temporary are different for the sub-towers.

• When I say "move N-1 from source to temp", it means source2 = source, dest2 = temp, and as a consequence temp2 = dest.
• When you move the bottom disk, all is unchanged ( 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 consequence temp4 = source.