Member Avatar for htq2511

hi everyone. i am working on the tower of Hanoi code and got a very interesting question.
Here is the code of Tower of Hanoi problem:

#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 );
//cout <<"   1   "<<endl;
// move n-1 disks from source to intermediate tower
cout << "disk " << n << " is moved from " << s << " to " << d << endl;
//cout <<"   2   "<<endl;
// move the disk from to source to destination
move( n-1,i,s,d );
//cout <<"   3   "<<endl;
// 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" );
}

in order to understand how 2 recursive function works at the same time. I added something up to the code:

#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
{
	cout <<"   0    s = "<< s <<" i = "<< i << " d= "<< d <<" disk ="<< n <<endl;

if( n > 0 )
{
cout <<"   1    s = "<< s <<" i = "<< i << " d= "<< d <<" disk ="<< n <<endl;
move( n-1,s,d,i );
cout <<"	2    s = "<< s <<" i = "<< i << " d= "<< d <<" disk ="<< n <<endl;
// move n-1 disks from source to intermediate tower
cout << "DISK " << n << " IS MOVED FROM " << s << " TO " << d << endl;
cout <<"   3   s = " << s << " i = "<< i << " d= "<< d <<" disk ="<< n <<endl;
// move the disk from to source to destination
move( n-1,i,s,d );
cout <<"	4    s = "<< s <<" i = "<< i << " d= "<< d <<" disk ="<< n <<endl;
// 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" );
}

it looks very hard to read, but if you can understand my idea, you will be able to read that.
If you dont like that, just run the original code.
the problem is when I typed the disk = 3 and the third step of this process is
[img][/img]
By htq at 2011-02-22
disk 1 will be moved back from the destination tower to intermediate tower.
But in the code, we just have 3 directions :

move( n-1,s,d,i );
//cout <<"   1   "<<endl;
// move n-1 disks from source to intermediate tower
cout << "disk " << n << " is moved from " << s << " to " << d << endl;
//cout <<"   2   "<<endl;
// move the disk from to source to destination
move( n-1,i,s,d );
//cout <<"   3   "<<endl;
// move n-1 disks from intermediate to destination

I have not see any direction that the disk would be moved from the destination tower to intermediate tower.
Have u guys ever mentioned that or did I miss something ?
i discovered that after the line move( n-1,i,s,d ); was applied (with disk = 1 currently) , it returned to the top of the function with disk = 1 and in here, it changed it value :
s= destination tower i= source tower d= intermediate tower
IF the function move( n-1,i,s,d ) is applied , it has to be :
s = intermediate i = source d= destination
but it did in the opposite direction.
I tried with disk = 2 and it worked exactly like the the marked code
Do you guys have any idea for this ?

  • 2 Contributors
  • 1 Reply
  • 180 Views
  • 14 Hours Discussion Span
  • Latest Post Latest Post by pseudorandom21

Dani AI

Generated

Short answer: that behavior is correct. Each recursive call gets its own local parameters, so the names s, i, d are re-bound inside each call. Because the two recursive calls pass the three pegs in different orders, a deep (inner) call can have its local s equal to the caller’s d — which produces the “destination → intermediate” move you saw.

For n = 3 the canonical move sequence is:

  1. small S → D
  2. medium S → I
  3. small D → I ← this is the step you observed
  4. large S → D
  5. small I → S
  6. medium I → D
  7. small S → D

If that still looks confusing when you print long strings, make the recursion structure explicit by printing a call-depth prefix (or use single-letter peg names or integers). That makes it obvious which call frame owns which name.

A small practical tip (and a couple of C++ fixes): prefer const char* or std::string for peg names and make your debug output use an indent/depth parameter so each call prints with an extra two spaces. Also follow ’s advice and use int main() returning 0, compile with warnings enabled (e.g. -Wall -Wextra) and remember the algorithm makes 2^n−1 moves — recursion and runtime grow fast, so keep n small or use an iterative/bitwise simulation for large n.

Example debugging signature to add a depth level:

void move(int n, const char* s, const char* i, const char* d, int depth = 0) {
    // print indentation using depth, then recurse with depth+1
}
Member Avatar for pseudorandom21

Do not use

void main()

use instead

int main()
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.