Towers of Hanoi

Question

I am working on an exercise in a book which asks us to solve the Towers of Hanoi problem using recursive methods. I have come to a solution, but from what I gather after browsing the Internet when done is that my solution may not be correct. Does anyone know a better/different way to solve the problem? And does anyone have nay suggestions for improvements. (Btw, the out put is correct. It is only supposed to tell from which tower to another pegs are moving, not specifically which pegs)

Here is the code:

#include <iostream>
#include <cmath>

using namespace std;

static int counter = 0;

void ToH(int dskToMv, int cLocation, int tmpLocation, int fLocation)
{
if (dskToMv == 0);
else
{
    if (dskToMv%2!=0)
    {
        cout << cLocation << "->" << tmpLocation << endl;
        cout << cLocation << "->" << fLocation << endl;
        cout << tmpLocation << "->" << fLocation << endl;
        ToH(dskToMv-1, cLocation, fLocation, tmpLocation);
    }
    else if (dskToMv%2==0)
    {
        counter++;
        if (counter%2==0)
            cout << fLocation << "->" << cLocation << endl;
        else
            cout << cLocation << "->" << fLocation << endl;
        ToH(dskToMv-1, tmpLocation, cLocation, fLocation);
    }
}
}

int main()
{
int x, j;
cout << "Enter number of disks: ";
cin >> x;
j = pow(2.0, x-1)-1;
if (x%2==0)
    ToH(j, 1, 2, 3);
else
    ToH(j, 1, 3, 2);
return 0;
}

Is this method qualified as recursion?

Answer 1

Here is a recursive solution for tower of hanoi.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

void move(vector<int>& frompeg, vector<int>& topeg) {
    topeg.push_back(frompeg.back());
    frompeg.pop_back();
}

void hanoi(vector<int>& frompeg, vector<int>& topeg, vector<int>& auxpeg, 
int num_disks) {
    if (num_disks == 1) {
        move(frompeg, topeg);
    }
    else {
        hanoi(frompeg, auxpeg, topeg, num_disks - 1);
        move(frompeg, topeg);
        hanoi(auxpeg, topeg, frompeg, num_disks - 1);
    }
}

void printpeg(vector<int> a, vector<int> b, vector<int> c) {
    cout << "a: ";
    for (int i = 0; i < a.size(); i++) {
        cout << a[i] << " ";
    }
    cout << "\n";
    cout << "b: ";
    for (int i = 0; i < b.size(); i++) {
        cout << b[i] << " ";
    }
    cout << "\n";
    cout << "c: ";
    for (int i = 0; i < c.size(); i++) {
        cout << c[i] << " ";
    }

}

int main() {

    int n;
    cin >> n;
    vector<int> a,b,c;
    for (int i = 0; i < n; i++) {
        a.push_back(n - i);
    }
    cout << "befor: " << endl;
    printpeg(a, b, c);
    hanoi(a, b, c, n);
    cout << "after: " << endl;
    printpeg(a, b, c);
    cin.get();
    cin.get();
    return 0;
    }

Answer 2

#include <iostream>

using namespace std;

void towers(int, char, char, char);

void towers(int num, char frompeg, char topeg, char auxpeg)
{
    if (num == 1)
    {

        cout<<"\n Move disk 1 from peg "<<frompeg<<" to peg "<<topeg<<endl;

        return;
    }

    towers(num - 1, frompeg, auxpeg, topeg);

    cout<<"\n Move disk "<<num<<" from peg "<<frompeg<<" to peg "   <<topeg<<endl;

    towers(num - 1, auxpeg, topeg, frompeg);
}

int main()
{
    int num;

    cout<<"Enter the number of disks : ";

    cin>>num;

    cout<<"The sequence of moves involved in the Tower of Hanoi are :\n"<<endl;

    towers(num, 'A', 'C', 'B');

    return 0;
}

Answer 3

Every recursion method has 3 steps

1) A check condition 2) Return value when check condition is satisfied. 3) A call to method itself

@Stargazer712 solution is perfect.

Answer 4

It's easiest if you look at the problem recursively:

To move N discs from A to B (using C):

1. if (N > 1) move N-1 discs from A to C (using B)
2. move one disc from A to B
3. if (N > 1) move N-1 discs from C to B (using A)

For any given call, whichever peg is not the source or the destination is the ancillary.

To answer your actual question: yes, your solution appears to be recursive, though a bit more complex than really necessary.

Answer 5

To answer your question: yes, that is qualified as recursion. Any time a function calls itself, it is recursion.

With that being said, your code can be trimmed down substantially:

#include <iostream>

using namespace std;

void ToH(int dskToMv, int cLocation, int tmpLocation, int fLocation)
{
    if( dskToMv != 0 ) 
    {
        ToH( dskToMv-1, cLocation, fLocation, tmpLocation );
        cout << cLocation << "->" << fLocation << endl;
        ToH( dskToMv-1, tmpLocation, cLocation, fLocation );
    }
}

int main()
{
    int x;
    cout << "Enter number of disks: ";
    cin >> x;
    ToH(x, 1, 2, 3);
    return 0;
}