CODEWITHSUNDEEP
calgorithmfunctionrecursion
user11
user11

Reputation: 197

unclear with this tower of hanoi recursive call

void TOH(int n,char x,char y,char z);
void main()
{
  int n;
  printf("nEnter number of plates:");
  scanf("%d",&n);
  TOH(n,'A','B','C');
  getch();
}

void TOH(int n,char x,char y,char z)
{
  if(n>0)
  {
    TOH(n-1,x,z,y);
    printf("n%c -> %c",x,y);
    TOH(n-1,z,y,x);
  }
}

In this coding i'm so confused with recursive call and how the characters and integers are handled in function call,can anyone explain with a simple demonstration.

Upvotes: 2

Views: 225

Answers (1)

Itay Karo
Itay Karo

Reputation: 18306

Generally - to solve the tower of hanoi problem with n plates you should:

  1. Move n-1 plates from A to C
  2. Move the single plate on A to B
  3. Move the n-1 plates from C to B

#1 is the same problem with n-1 instead of n plates when the towers are ordered A, C, B
#3 is the same problem with n-1 instead of n plates when the towers are ordered A, B, A

For example:
for n = 3
1. Move 2 plate from A to C
2. Move the single plate on A to B
3. Move the 2 plates from C to B

#1 is mapped to the call TOH(n-1,x,z,y);
#2 is mapped to the call printf("n%c -> %c",x,y);
#3 is mapped to the call TOH(n-1,z,y,x);

EDIT - example
So this will be the order of the calls (indentation is a recursive call)

  • TOH(3, 'A', 'B', 'C') // move 3 plates from A to B
    • TOH(2, 'A', 'C', 'B') // move 2 plates from A to C
      • TOH(1, 'A', 'B', 'C') // move one plate from A to B
      • move one plate from A to C
      • TOH(1, 'B', 'C', 'A') // move one plate from B to C
      • // Now we have 1 plate in A and 2 plates in C
    • move one plate from A to B
    • TOH(2, 'C', 'B', 'A') // move 2 plates from C to B
      • TOH(1, 'C', 'A', 'B') // move one plate from C to A
      • move one plate from C to B
      • TOH(1, 'A', 'B', 'C') // move the last plate from A to B
      • DONE - ALL PLATES ARE IN PLACE

Upvotes: 5

Related Questions