Tower of Hanoi

I am working on a problem for school and it involves recursion. My exercise ask me to write a program that solves the tower of hanio using recursion. I have gone out and found a number of examples but I am unclear on how the program works. Can someone explain this concept to me? Thanks

DMKanz07

Broad question. Broad answer.

Note the nice gif image.

Oh, and there just so happens to be a recursive algorithm located on the page with C code written for you. I doubt you'll be able to copy it directly, but you can definitely learn from it.

This is the one example I found. I am not sure I fully understand what is happening in this program. Any guidance would be appreciated.

Code:

#include<stdio.h>

/* Function Prototype */
void towers( int number, int peg1, int peg3, int peg2 );

/* Function main begins program execution */ 
main()
{

    int number; /* Variable in which number will be stored */
    
    printf( "Enter total no. of disks: " ); /* Prompt for input */
        scanf( "%d",&number ); /* Read number from user */
        towers( number, 1, 3, 2 ); /* Function called */

} /* End function main */

/* Towers function definition */
void towers( int number, int peg1, int peg3, int peg2 )
{

    if( number == 1 ){
        printf( "%d --> %d\n", peg1, peg2 );
        return; /* Indicates that program ended successfully */
    } /* End if */ 
    
    towers( number - 1, peg1, peg2, peg3 );
        printf( "%d --> %d\n", peg1, peg2 );
    towers( number - 1, peg3, peg1, peg2 );
    
} /* End function towers */

The output for 3 disk is
1 --> 2
1 --> 3
2 --> 3
1 --> 2
3 --> 1
3 --> 2
1 --> 2

Can you explain the function and how it knows what number goes where? This is very confusing to me.

Thank you

DMKanz07

Perhaps before you go any further with programming stuff like this, you should make sure you understand how the algorithm works.

For example, can you intuitively do the solution "by hand"? If so, can you then express the algorithm in English (or any other natural language) step by step? If so, then work on translating your natural language instructions into C.

For me personally, I never liked pseudo code and I hated listing all of my steps out. I rarely (never?) do that before starting a program, but I do think the program through and try to have an entire idea of how I'm going to get it done before I even start. If I get stuck on something not working or something difficult, I'll manually trace it out on paper and draw all kinds of notations that I'm unsure that anyone else can read.

Now with that said, is your problem related to the Towers of Hanoi problem, or is it related to recursion?

The numbers are just showing when to move the ring from tower x to tower y. That particular list of numbers, I believe, will get you from all of the rings on tower 1 to tower 2.

You been very helpful thanks

DMKanz07

Been awhile, but in the Towers of Hanoi, there's a simple trick:

If the pile of disks you want to move is odd, then move the first disk to the peg you want them to rest upon, when that stack or sub stack, is completely moved. If the number of disks you need to move is even, then move the first disk to the peg you DO NOT want them to ultimately rest upon.

The thing with the game that's tough is that in order to make a move with more disks, you have to make more "sub stacks", in order to complete your move. It's hard to remember which sub stack needs to be moved next and in general, just where you are in the order of moves and sub-moves, that are needed to win the game.

Always remember the odd and even trick though - it's true for all moves, and for all the little sub moves you make, anywhere in the course of the game.

So if you have 3 disks, on the leftmost peg, and you want to move those disks to the center peg ultimately, move the first disk on your first move, from the leftmost peg to the center peg, Next disk move is left to right, then center to right, then left to center.

Now you have to move a 2 disk sub stack to move from right to center. Since it's an even number of disks to be moved, move is right to left (away from final goal peg), then right to center, and finally left to center.

If you have a lot of disks to move, it helps if they're numbered or REALLY have large steps in their sizes, to easily keep track of each sub stack, and not get mucked up by taking one disk to many or too few, on a sub stack move.

Adak

What I find incredibly amazing about the Towers of Hanoi problem is how simple the reasoning behind the recursive algorithm is. You can sit there and think about the solution for hours without grasping the concept:

To move n disks from peg A to peg B:

• Move n−1 disks from A to C. This leaves the nth disk alone on peg A;
• Move the nth disk from A to B;
• Move n−1 disks from C to B so they sit on the nth disk.

That's all you need to know. Think about it, understand it (!) and then write it.

I am comfortable with how you make the moves. What I am confused on is how does the program know what number to display in the output.

towers( number - 1, peg1, peg2, peg3 );
printf( "%d --> %d\n", peg1, peg2 );
towers( number - 1, peg3, peg1, peg2 );

In the printf statement it calls for peg1 and peg2. The first move is 1 --> 2 the second move is 1 --> 3. Why would this not repeat 1 --> 2. I am looking for an explanation on the syntax of the function. I hope this make sense. Still learning C

Thanks

DMKanz07

If you gave the variables better names, say like this

towers( number - 1, from, spare, to ); // move n-1 to the spare, using 'to' as a workspace
printf( "%d --> %d\n", from, to ); // move the bottom disk
towers( number - 1, spare, to, from ); // move n-1 from the spare, using 'from' as the workspace

Does that help visualise the problem?

not really

again how does the function print a 1, 2 or 3 if the printf statement is calling for from and to variable

this is very confusing to me - sorry

thanks

dmkanz07

Well single step the code with a tower of two disks.
Then do it with 3 disks.

Look in the code, where the function is called the first time:

Code:

towers( number, 1, 3, 2 ); /* Function called */

Here, you're actually attributing the numbers to the different parameters, which will later on be printed out.

Does it reassign values to from and to each time thru the recursion until number == 1. If so, in the first part of the functions is it safe to assume that if you have three disk that it reads

tower(number-1, from, to, spare) = tower( 3-1, 1, 2, 3)

is this correct

Thanks

DMKanz07

Originally Posted by dmkanz07

Does it reassign values to from and to each time thru the recursion until number == 1. If so, in the first part of the functions is it safe to assume that if you have three disk that it reads

tower(number-1, from, to, spare) = tower( 3-1, 1, 2, 3)

is this correct

Thanks

DMKanz07

All recursive functions have a base case so it can figure out when to stop. You probably DON'T want to label the pegs from, to, and spare, because the from to and spare will change with the move, and maybe it won't confuse the computer, but it darn sure will confuse the poor human!

In parameter passing, it is done by THEIR ORDER in the parameter list - NOT by their name. So a parameter of (peg1, peg2) may be received by the functions with (peg_1, peg_2), but if I change the calling parameters to (peg3, peg2), and keep the receiving parameters the same, now peg3 will be copied into the receiving functions peg_1, and the second parameter will be copied into the second receiving functions parameter of peg_2.

Remember that ALL parameters in C are passed by a copy mechanism, not the actual parameter itself. Pointers APPEAR to be passing the same parameter, but they don't, either. It just LOOKS like they do, because the copied memory address received by the function, is just as good as the original, so IN EFFECT, it's a call which includes the original parameter - but it's not.

Say you have a variable int number in main(), and you call another function like this:
AnotherFunction(number);

Now in AnotherFunction, the variable "number", is NOT the same variable as the "number" variable in main(). It is a copy, and if AnotherFunction wants to receive that copied "number" variable, with another name, it's perfectly free to do so:
void AnotherFunction(int AliasNameForNumberInMain)

Hope that helps.

Adak