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

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.

This article has been dead for over six months. Start a new discussion instead.