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;
}

It would probably be a lot less confusing if it was indented -_- — Konrad Lindenbach, Aug 28 '13 at 13:17
Recursion isn't as confusing as recursion isn't as confusing as recursion isn't as confusing as... — temporary_user_name, Aug 28 '13 at 13:18
This is the canonical recursive solution to the Towers of Hanoi problem: http://www.cs.cmu.edu/~cburch/survey/recurse/hanoiimpl.html — SubSevn, Aug 28 '13 at 13:19
If I am not asking for too much, How does the program work in general? — Boyd Smith, Aug 28 '13 at 13:23
Take paper and pencil and start executing program yourself. Or use debugger to step by step execution and see variable values. — Rohan, Aug 28 '13 at 13:23
@BoydSmith the link that SubSevn provided contains an explanation — Hulk, Aug 28 '13 at 13:28
@Rohan Ok. How does the program work from if(n>0). Like how the variables are stored in stack — Boyd Smith, Aug 28 '13 at 13:28
@Hulk I perfectly understand Tower of henoi. All I want to know is how the program works? — Boyd Smith, Aug 28 '13 at 13:29

score 4 · Answer 1 · answered Aug 28 '13 at 13:30

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.

score 2 · Accepted Answer · answered Aug 28 '13 at 14:22

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.

I want to add something: The output of the recursive solution for the Tower of Hanoi problem is a set of instructions on how to solve the problem in real life. Look for a video on the internet about the real-life problem and you will get what I mean. — carloswm85, Jul 24 '18 at 16:35

Understanding recursive solution to Towers of Hanoi

2 Answers2