By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
432,526 Members | 1,895 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 432,526 IT Pros & Developers. It's quick & easy.

Recursion please explain this

P: 11
hey someone posted towers of hanoi code on here.. I have this assignment in my programming class now.. I obviously can take this code and modify it but i just want to understand how this works I cant turn this in not knowing whats going on here. Could someone please explain to me what is going on when the program enters hanoi (nDisks - 1, pegA, pegC, pegB); that function? What is the purpose for switching the order of pegA, B, and C? this is the entire code..

Expand|Select|Wrap|Line Numbers
  1. #include <iostream>
  2. using namespace std;
  3. void hanoi (int nDisks, int pegA, int pegB, int pegC);
  4. int count = 0;
  5.  
  6. int main ()
  7. {
  8.     int n;
  9.  
  10.     cout << "Input number of disks: ";
  11.     cin >> n;
  12.  
  13.     hanoi (n, 1, 2, 3);
  14.     cout<<"Number of moves required: "<<count<<endl;
  15.  
  16.     return 0;
  17. }
  18.  
  19. void hanoi (int nDisks, int pegA, int pegB, int pegC)
  20. {
  21.     if (nDisks>0) 
  22.     {
  23.         hanoi (nDisks - 1, pegA, pegC, pegB);
  24.  
  25.  
  26.         cout << "Move disk from peg " << pegA << " to peg " << pegC << endl;
  27.  
  28.         hanoi( nDisks-1, pegB, pegA, pegC);
  29.  
  30.         count++;
  31.     }
  32. }
Mar 8 '07 #1
Share this Question
Share on Google+
13 Replies


Ganon11
Expert 2.5K+
P: 3,652
Let me suggest that you get rid of this code, now, and write your own. TSDN doesn't support plagiarism, and your teacher might get wise as give you a 0 for cheating.

The best way for you to understand how a program works is to write it on your own. Come up with a general solution for solving a TOH puzzle, and then turn that solution into an algorithm.
Mar 8 '07 #2

P: 11
Did I anywhere suggest that I was planning on turning this code in? I posted the code asking if someone can explain to me how this is actually working. Then after gaining an understanding I can write my own code.. thanks for the help though
Mar 8 '07 #3

Ganon11
Expert 2.5K+
P: 3,652
I obviously can take this code and modify it but i just want to understand how this works I cant turn this in not knowing whats going on here.
By this, I thought you meant you would be turning it in, but not until you understood it. Sorry for any misunderstanding and/or harshness on my part.
Mar 8 '07 #4

P: 11
By this, I thought you meant you would be turning it in, but not until you understood it. Sorry for any misunderstanding and/or harshness on my part.
No, I may have worded that wrong. I simply got the code off of here earlier today in an attempt to debug and try to figure out how it works. I just dont understand what is going on with the two function calls.. What do the variables in the arguement actually do? ie. pegA, pegB, pegC.. and the n-1? I just cant grasp what is going on here.
Mar 8 '07 #5

P: 2
hey someone posted towers of hanoi code on here.. I have this assignment in my programming class now.. I obviously can take this code and modify it but i just want to understand how this works I cant turn this in not knowing whats going on here. Could someone please explain to me what is going on when the program enters hanoi (nDisks - 1, pegA, pegC, pegB); that function? What is the purpose for switching the order of pegA, B, and C? this is the entire code..

Expand|Select|Wrap|Line Numbers
  1. #include <iostream>
  2. using namespace std;
  3. void hanoi (int nDisks, int pegA, int pegB, int pegC);
  4. int count = 0;
  5.  
  6. int main ()
  7. {
  8.     int n;
  9.  
  10.     cout << "Input number of disks: ";
  11.     cin >> n;
  12.  
  13.     hanoi (n, 1, 2, 3);
  14.     cout<<"Number of moves required: "<<count<<endl;
  15.  
  16.     return 0;
  17. }
  18.  
  19. void hanoi (int nDisks, int pegA, int pegB, int pegC)
  20. {
  21.     if (nDisks>0) 
  22.     {
  23.         hanoi (nDisks - 1, pegA, pegC, pegB);
  24.  
  25.  
  26.         cout << "Move disk from peg " << pegA << " to peg " << pegC << endl;
  27.  
  28.         hanoi( nDisks-1, pegB, pegA, pegC);
  29.  
  30.         count++;
  31.     }
  32. }

Actually this code works on the principle
To move n disks from one source peg to the destination peg, U hav to first move n-1 disks to the middle peg using it as a temporary peg, and then move the last disk from the source to destination peg and then continue in this way till all the disks hav been moved.

Example":

to move 3 disks from source (peg 1) to the destination (peg3), U hav to first move 2 disks to the middle peg (peg2), using it as a temporary peg...

But now to move 2 disks from peg1 to peg2, U hav to move 1 disk from peg1 to peg 3 and then one from peg1 to peg2...
So the chain continues till all disks hav been moved..
Hope U understand. if not then let me know at <email removed>
Mar 8 '07 #6

P: 11
Well, I have figured it out and written my own version of the code.. I sat here trying to keep my eyes open for a couple of hours over this one.. I came to the conclusion that in my move function i am originally wanting to move 1 disk which would be disk -1 from peg1 to peg3 using peg2 as the temp holding area... so in the function i arranged peg1, then peg3 to achieve this then peg2 at the end of the arguement.. did some output then after the top function quit when disks -1 was 0 the next function i had one final disk( i made this example with 2 disks) i wanted the final disk which was the top one to move from the holding position on peg2 to the final peg (peg3) so i arranged them like so in the function arguement.. in the order that i wanted things to happen on small scale.. and it seems to be correct for any size! Is that how i should be looking at it? Here is my code.. Keep in mind I had already edited some things on the first example code that I posted it was actually laid out differently so i didnt copy!

Expand|Select|Wrap|Line Numbers
  1. #include <iostream>
  2. using namespace std;
  3. void move( int disks, int peg1, int peg2, int peg3);
  4. int count = 0;
  5.  
  6. void main()
  7. {
  8.     int disks = 0;
  9.     cout<<"How many disks?"<<endl;
  10.     cin>> disks;
  11.     move( disks, 1, 2, 3);
  12.     cout<<"Moves required: "<< count<<endl;
  13. }
  14.  
  15. void move( int disks, int peg1, int peg2, int peg3)
  16. {
  17.     if(disks > 0)
  18.     {
  19.         move(disks - 1, peg1, peg3, peg2);
  20.         cout<< peg1<< "-->" << peg3<<endl;
  21.         move(disks -1, peg2, peg1, peg3);
  22.         count++;
  23.     }
  24. }
Mar 8 '07 #7

Ganon11
Expert 2.5K+
P: 3,652
It looks right to me, but for some reason it won't compile on my computer. Are you sure you can use void main()? My compiler wants it to be int main().
Mar 8 '07 #8

P: 94
Have you tried to make it int main ?
Just return 0.

Just a question ;-)
Mar 8 '07 #9

Ganon11
Expert 2.5K+
P: 3,652
I did - that one of the things I had to do to make it C++worthy.

But my compiler is giving me trouble in declaring int count = 0; outside of main(). It says that main() and move() can't see count - it's undeclared.
Mar 8 '07 #10

P: 94
I did - that one of the things I had to do to make it C++worthy.

But my compiler is giving me trouble in declaring int count = 0; outside of main(). It says that main() and move() can't see count - it's undeclared.
That's funny, I ran it in Visual Studio, In linux and I ran it with a borland compiler and I didn't get any problems...

Whether it is void or int.

;-)
Mar 8 '07 #11

P: 11
Yeah, that is weird that you guys are having compiler troubles with this... Im using Crimson editor and borland as my compiler and it works.. I also ran it through in visual studio and didnt get problems. I'll mess around with it a little more.
Mar 8 '07 #12

P: 11
I did - that one of the things I had to do to make it C++worthy.

But my compiler is giving me trouble in declaring int count = 0; outside of main(). It says that main() and move() can't see count - it's undeclared.
That doesnt really make sense why main() or move() cant see count.. its a global variable?
Mar 8 '07 #13

Ganon11
Expert 2.5K+
P: 3,652
Yeah, I copied your code exactly - all I changed was making main into int main(), adding a return 0 at the end (to match the int main()) and adding a system("PAUSE"); command to freeze the output, and it won't compile for me. How weird.
Mar 8 '07 #14

Post your reply

Sign in to post your reply or Sign up for a free account.