Towers of Hanoi Recursive

[jghost]

Ok this is the classic Towers of Hanoi question. Legend has it that in a temple in the Far East, priest are attempting to move a stack of disks from one peg to another. The initial stack had 64 disks threaded onto one peg and arranged from bottom to top by decreasing size. The priests are attempting to move the stack from this peg to a second peg under the constraints that exactly one disk is moved at a time, and at no time may a larger disk be placed above a smaller disk. A third peg is available for temporarily holding disks.

Let us assume that the priests are attempting to move the disks from peg 1 to peg 3. We wish to develop an algorithm that prints the precise sequence of peg-to-peg disk transfers.

I have the program and it runs perfect. I couldn't figure it out but I found it online ( I know some disagree with this but I tried for a while to figure this out and I couldn't. I'm trying to understand the logic behind it, not just copying the code ). My only problem is how the recursive function executes. I don't understand it's path for the variable n. I understand recursion breaks down a problem to a base. This one just seems weird. I even watched the variable n in the watch window. ( I use visual studio 2008 ). I also searched the forums for this problem and I saw a good amount of threads but none helped with my confusion.

When it first enters the function ( assume I choose 3 for number of disks ). After step 3 it exits the function but then something weird happens. It re-enters the function with n value of 1 and then it continues to the cout statement and outputs #1 disk.

if( n > 0 ) check for if step1, check if step2, check if step3, check if step8
{
move( n-1,s,d,i ); step1, n-1 n = 2, step2 n-1 n=1, step3 n-1 n=0, step5 reenter with n=1, step10 n=2 at this line
// move n-1 disks from source to intermediate tower
cout << "disk " << n << " is moved from " << s << " to " << d << endl; step6 output n=1 value, step11 output n=2
// move the disk from to source to destination
move( n-1,i,s,d ); step7 n-1 n= 0, step10 re-enter with n=1
// move n-1 disks from intermediate to destination
}
} step4 exit function, step9 exit function,

And the function continues along it's path until it solves the Towers of Hanoi problem. I can't follow this recursive function and I really want to understand the logic behind it. Also the way the variables s d i are swapped lost me too as far as printing the correct tower to move the disks to. So if anyone could help explain it would be greatly appreciated. I want to understand this program fully before I move on. Here is the full program:

#include<iostream>

using namespace std;

void move( int n, char*s, char*i, char*d )
// s stands for source tower
// d stands for destination tower
// i stands for intermediate tower
{
if( n > 0 )
{
move( n-1,s,d,i );
// move n-1 disks from source to intermediate tower
cout << "disk " << n << " is moved from " << s << " to " << d << endl;
// move the disk from to source to destination
move( n-1,i,s,d );
// move n-1 disks from intermediate to destination
}
}

void main()
{
cout << "\n************************************************ **********\n";
cout << "This C++ program is to solve the towers of hanoi problem";
cout << "\n************************************************ **********\n";
cout << "Enter the no. of disks ";
int n;
cin >> n;
move( n, "source tower", "intermediate tower", "destination tower" );
}

[VernonDozier]

void move( int n, char*s, char*i, char*d )
// s stands for source tower
// d stands for destination tower
// i stands for intermediate tower
{
    if( n > 0 )
    {
        move( n-1,s,d,i );
        // move n-1 disks from source to intermediate tower
        cout << "disk " << n << " is moved from " << s << " to " << d << endl;
        // move the disk from to source to destination
        move( n-1,i,s,d );
        // move n-1 disks from intermediate to destination
    }
}

You might want to change the code from "source", "intermediate", and "destination" to "1,", "2", and "3" since everything keeps flipping back and forth. This is a real step-by-step process. Follow it on paper. Start with 1 disk. Run the program. Then do it with 2 when you feel you've gotten the hang of 1. Follow it step by step. Then do 3 disks. Repeat.

Every recursive function has a "base condition" where it no longer calls itself. In this case, it's when there are 0 disks and hence nothing to move.

I've added some cout statements. Note the number of times each line is displayed. Line 2 is displayed 2^n - 1 times, which is the exact number of moves total. Note than line 1 is displayed n times before line 2 is displayed at all, and the last n displays are line 3. That'll give you an idea of how the "call stack" works and how line 1 will continually be displayed until the base condition is met, then line 2 will be displayed. Also note how line 2 is never displayed twice in a row.

It takes a while to get a good feel for recursion and call stacks and how they operate. If you have a debugger, stick some breakpoints at each line and step through the program. It'll give you a great idea of how it works. The revised function with cout statements (poor man's break statement) is below. Hope this helps.

void move( int n, char*s, char*i, char*d )
// s stands for source tower
// i stands for intermediate tower
// d stands for destination tower
{
    if( n > 0 )
    {
        cout << "Line 1 : Moving top " << n - 1 << " disks of " << s << " to " << i << ".";
        if ( n - 1 <= 0)
            cout << "  There will be nothing to move.  Base condition will be hit.";
        cout << endl;             
        move( n-1,s,d,i );
        // move n-1 disks from source to intermediate tower
        
        
        cout << "Line 2 (Physically moving single disk) : Disk " << n << " is moved from " << s << " to " << d << endl;
        // move the disk from to source to destination
        
        
        move( n-1,i,s,d );
        // move n-1 disks from intermediate to destination
        cout << "Line 3 : Moving top " << n - 1 << " disks of " << i << " to " << d << ".";
        if ( n - 1 <= 0)
            cout << "  There will be nothing to move.  Base condition will be hit.";
        cout << endl;
    }
    else
        cout << "Line 4 : End of recursion.  Base condition has been met.\n";
}

[jghost]

I understand what you're saying and it helps somewhat. I did do a break point before at if ( n > 0 ) and that is how I got the steps that I added to in my post. I added the breakpoint and stepped through the program. There are certain points I still don't understand. Do you see in my function with the step 10 where it re-enters the function at n=1 and then it goes straight to the output statement and outputs n=2. Why does it just jump straight to the output statement? And how does it go from n=1 on step 10 to outputing n=2 on step11

[VernonDozier]

Perhaps the following program will help you get a feel for what is going on and the order that it is going on. It's the same program, but with nested statements. The indentation relates to the depth of the call stack. Bigger call stack = more indentation. I indented the actual moving of the disks slightly further to make them "nested" within a larger process, but that doesn't correspond exactly to the depth of the call stack. Hopefully this doesn't just confuse things more. I added "depth" to the display to correspond to the depth of the call stack. If you use a debugger with the program and look at the call stack, hopefully that will make the nesting and depth display more clear.

Hope this helps.

#include<iostream>

using namespace std;


void move( int numNestedCalls, int n, char*s, char*i, char*d )
// s stands for source tower
// d stands for destination tower
// i stands for intermediate tower
{
    static int stepNumber = 0;
    
    
    if (n > 0)
    {
        for (int j = 0; j < 3 * numNestedCalls; j++)
            cout << " ";
            
        stepNumber += 1;
        cout << "Move " << n << " disks from " << s << " to " << d << " (depth = " <<
             numNestedCalls << ", step " << stepNumber << ")\n";
    }
    
    if( n > 0 )
    {
        move( numNestedCalls + 1, n-1,s,d,i );
        // move n-1 disks from source to intermediate
        
        stepNumber += 1;
        for (int j = 0; j < 3 * numNestedCalls + 3; j++)        
            cout << " ";
        cout << "disk " << n << " is moved from " << s << " to " << d << " (depth = " <<
            numNestedCalls << ", step " << stepNumber << ")\n";
        // move the disk from to source to destination
        
        move( numNestedCalls + 1, n-1,i,s,d );
        // move n-1 disks from intermediate to destination
    }
    
    if (n > 0)
    {
        stepNumber += 1;
        for (int j = 0; j < 3 * numNestedCalls; j++)
            cout << " ";
        cout << "End Move " << n << " disks from " << s << " to " << d << " (depth = " <<
             numNestedCalls << ", step " << stepNumber << ")\n";
    }    
}

int main()
{
    cout << "\n************************************************ **********\n";
    cout << "This C++ program is to solve the towers of hanoi problem";
    cout << "\n************************************************ **********\n";
    cout << "Enter the no. of disks ";
    int n;
    cin >> n;
    move( 1, n, "1", "2", "3" );
    
    cin.get (); // pause for input so screen doesn't disappear
    cin.get (); // pause for input so screen doesn't disappear
    return 0;
}

[jghost]

I really appreciate you putting that code together for me. I've analyzed it and debugged it a few times. I follow it somewhat but it sort of confuses me a little more to be honest :o maybe I am just not ment to get this. This is the only problem I don't understand in the book. Why can't this be easy like arrays :(

[angelbellz]

please i need a code with three towers and 64 disks of different sizes where the largest is gonna be at the bottom and the smallest at the top and only one disk can be moved at a time.no big disk resting on a smaller disk..each dik sitting on a tower except when being moved.this is really difficult.