## 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 422

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.