Towers of Hanoi

[Peyton]

Hi there,

I have been trying to figure out the common recursion problem given in e.g. 6.42 in the following link: Towers of Hanoi. After a few hours I still can't figure it out, even though I've got the code:

#include <iostream>

using namespace std;

//               num disks
void Towers(int numToMove, int initialPeg, int finalPeg, int holdingPeg)
{
    // 1, 3, 2
    if(numToMove == 1)
    {
            cout << initialPeg << "->" << finalPeg << endl;
    }
    else if(numToMove > 1)
    {
        Towers(numToMove - 1, initialPeg, holdingPeg, finalPeg); // 1, 2, 3
        cout << initialPeg << "->" << finalPeg << endl;
        Towers(numToMove - 1, holdingPeg, finalPeg, initialPeg); // 3, 2, 1
    }
}

int main()
{
    Towers(3, 1, 3, 2);     // move stack from peg 1 to 3, using peg 2 as holding peg
    return 0;
}

Can someone please explain how this works. I just don't get it, even though e.g. 6.42 pretty much explained how :P

[csurfer]

This is one classical example of recursion. I hope you know the rules of this problem.

Here you have three stands say a b c where where n pegs are inserted into a from 1 to n numbering where 1 is on top and 2 below it 3 below 2 and likewise to n.
Rule is larger number cannot come over smaller number and you need to get all pegs in same order finally to stand c or 3 as per your program.

Program :
In it you are calling a recursive function towers which has number of pegs left to move source and destination stands using an intermediate stand.

if(numToMove == 1)
{
cout << initialPeg << "->" << finalPeg << endl;
}

here you say if there is only one peg then move it from stand one to stand three directly objective attained.

else if(numToMove > 1)
{
Towers(numToMove - 1, initialPeg, holdingPeg, finalPeg); // 1, 2, 3
cout << initialPeg << "->" << finalPeg << endl;
Towers(numToMove - 1, holdingPeg, finalPeg, initialPeg); // 3, 2, 1
}

Here you say that if its more than one peg to move assume the problem is just for actual - 1 number of pegs and solve it.

That is if you can't solve for 5 pegs solve for 4 pegs and then for five similarly all conditions narrow down to just one which is always solvable.

You have the best explanation here.