C++ Towers of Hanoi - Recursion

[venros]

Hi guys,

I was messing with this for hours till it finally works, but honeslty half way through it starts going backwards so for example I have m,b,a,c and it couts a then c ( so b to c, instead it does c to b). Im not sure why that is (stack?)

would really appreciate the help ty.

EDIT:

Mind you even though its going backwards, its giving me the correct results every time, but this is more to understand what is going on in the background better.

#include <iostream>

using namespace std;


//Write a recursive algorithm to solve the towers of Hanoi problem.
//move disc 1 A to c ACB
//move disc 2 A to b ABC
//move disc 1 C to b CBA
//move disc 3 A to c ACB
//move disc 1 B to a BAC
//move disc 2 B to c BCA
//move disc 1 A to c ACB


int moves(0);
void Hanoi(int m, char a, char b, char c);

void Hanoi(int m, char a, char b, char c){
  moves++;
  if(m == 1){
    cout << "Move disc " << m << " from " << a << " to " << c << endl;
  }else{  
    Hanoi(m-1, a,c,b);
    cout << "Move disc " << m << " from " << a << " to " << c << endl;
    Hanoi(m-1,b,a,c);
  }
}

int main(){

  int discs;
  cout << "Enter the number of discs: " << endl;
  cin >> discs;
  Hanoi(discs, 'A', 'B', 'C');
  cout << "It took " << moves << " moves. " << endl;

  system("pause");
}

[kbw]

That isn't solving the Tower of Hanoi problem. You're supposed to move a stack of items (the tower) from one column to another, while obeying certain rules.

[venros]

What do you mean? I ran it multiple times and it does it perfectly by abiding of said rules. Can you please clarify?

It tells you step by step on what to move, etc. I just need to understand the recursion a little better (that is what im practicing, not actually creating a ToH).

[kbw]

Ok, I got it. You're just printing the steps and not displaying the towers at each step. And that's why you don't have a data structure that represents the towers.

[venros]

ya im still very new, I just need help with why at the 2nd recursion it goes in backwards, like BAC is supposed to print B to C, but instead it prints C to B.

[kbw]

It's not going backwards. That's clear if you print the state of the towers.

Your code is moving the tower from A to C. It looks like this:

  A     B     C 

  x 
 xxx 
xxxxx xxxxx xxxxx 


 xxx 
xxxxx         x 



xxxxx  xxx    x


        x 
xxxxx  xxx 


        x 
       xxx  xxxxx 



  x    xxx  xxxxx 


             xxx 
  x         xxxxx 

              x 
             xxx 
            xxxxx 

[venros]

I know what it is doing in terms of the move, what I dont understand is how the recursion is switching to the point that :

B-A-C
becomes
C-A-B

at no point am I switching the As with the C position

[kbw]

at no point am I switching the As with the C position

That's exactly what your code is doing. Can't you see that?

I dont understand is how the recursion is switching to the point that ...

Trace it by hand, look at your output and look at the diagrams I produced from your output.