moving of disc in tower of hanoi

Question

Please explain to me the recursion process step by step using F7.

I just can't correlate the return with flow of control.

#include<stdio.h>
#include<conio.h>

void t_of_h(char, char, char, int);

void main()
{
    int n;
    clrscr();

    printf("Enter no of DISC in Tower of Hanoi : ");
    scanf("%d",&n);

    printf("\nTower of Hanoi using %d DISCS\n",n);

    t_of_h('X', 'Y', 'Z', n);
    getch();
}

void t_of_h(char p1, char p2, char p3, int n)
{
   if(n==0)
     printf("Unsuccessful move\n");
   if(n==1)
     printf("Move DISC from %c to %c\n",p1,p3);
   else
   {
      t_of_h(p1,p3,p2,n-1);
      t_of_h(p1,p2,p3,1);
      t_of_h(p2,p1,p3,n-1);
   }
}

Answer 1

How do you move N disks from tower A to tower B?

1. Move N-1 disks from tower A to tower C.
2. Move the bottom disk from tower A to tower B.
3. Move N-1 disks from tower C to tower B.

The code is a pretty direct implementation of that. If you assume that you can move an arbitrary number of disks from one tower to another, then this clearly works. How do you move N-1 disks from tower A to tower C? Well, you move N-2 disks from tower A to tower B, then move the N-1th disk from tower A to tower C, then move the N-2 disks form tower B to tower C. And repeat...

Eventually, the recursion stops because you have a single disk to move.

An interesting exercise is "write a test harness that ensures that no invalid moves are ever made".

---

OK - I've run the code. Its visualization of the process is gruesome. It is very hard to see what is going on. But it is a direct report of what the algorithm does. Now what?

1 disk

Enter no of DISC in Tower of Hanoi : 1

Tower of Hanoi using 1 DISCS
Move DISC from X to Z

2 disks

Enter no of DISC in Tower of Hanoi : 2

Tower of Hanoi using 2 DISCS
Move DISC from X to Y
Move DISC from X to Z
Move DISC from Y to Z

Note that it is moving disks from X to Z. How do you move 2 disks from X to Z? Move the top disk from X to Y. Move the bottom disk from X to Z. Move the original top disk from Y to Z.

3 disks

Enter no of DISC in Tower of Hanoi : 3

Tower of Hanoi using 3 DISCS
Move DISC from X to Z
Move DISC from X to Y
Move DISC from Z to Y
Move DISC from X to Z
Move DISC from Y to X
Move DISC from Y to Z
Move DISC from X to Z

Answer 2

Using F7?

Well if you are having trouble understanding the recursion, get out a pen and paper and step through the program. Stack each call with the correct arguments.

It should be simpler when you can visualise it.