Towers of Hanoi: recursion question

[aikiart]

Good day,

I'm having problems seeing how the recursion is working with this program. I've traced it but I don't understand why after if(num >0) is false it returns to the statement following the last function call and then seems to start the recursion again, but backwards? What I see when I trace it is that the program decrements num to zero, it then seems to exit and goes to right after the 2nd to last "}" line 12 in the code fragment but then it return to line 8, why doesn't it just return to the main program?

any help is appreciated.

void moveDiscs(int num, int fromPeg, int toPeg, int tempPeg)
{
   if (num > 0)
   {//added to watch the variables
           cout << "fromPeg: toPeg: tempPeg: " << endl;
           cout << "   " << fromPeg << "   " << toPeg << "   " << tempPeg << endl;
      moveDiscs (num - 1, fromPeg, tempPeg, toPeg);
      cout << "Move a disc from peg " << fromPeg (program then goes to here and calls moveDiscs again at line 10. 
           << " to peg " << toPeg << endl;
      moveDiscs(num - 1, tempPeg, toPeg, fromPeg);(then here and starts the recursion again)
   }
}program goes to here when num >0 fails) it then goes to back to line 8

Here's the program:

// This program displays a solution to the Towers of
// Hanoi game.
#include <iostream>
using namespace std;

// Function prototype
void moveDiscs(int, int, int, int);

int main()
{
   const int NUM_DISCS = 3;   // Number of discs to move
   const int FROM_PEG = 1;    // Initial "from" peg
   const int TO_PEG = 3;      // Initial "to" peg
   const int TEMP_PEG = 2;    // Initial "temp" peg
   
   // Play the game.
   moveDiscs(NUM_DISCS, FROM_PEG, TO_PEG, TEMP_PEG);
   cout << "All the pegs are moved!\n";
   system("pause");
   return 0;
}

void moveDiscs(int num, int fromPeg, int toPeg, int tempPeg)
{
   if (num > 0)
   {
           cout << "fromPeg: toPeg: tempPeg: " << endl;
           cout << "   " << fromPeg << "   " << toPeg << "   " << tempPeg << endl;
      moveDiscs (num - 1, fromPeg, tempPeg, toPeg);
      cout << "Move a disc from peg " << fromPeg
           << " to peg " << toPeg << endl;
      moveDiscs(num - 1, tempPeg, toPeg, fromPeg);
   }
}

[Fbody]

In recursion, you get several copies of a function all running at the same time with each subsequent copy running inside the previous one. Once the end condition is met, the inner-most copy of the function returns causing the rest of the copies to return and send their information back to the outer copies of the function.

It's similar to twisting up the chains of a swing, at some point you have to let go. When you finally do let go, they'll untwist in reverse order.

In Towers of Hanoi, a move is a 2-step process. In order to move a disc, you have to clear all the discs above it first. Take a closer look at the calls to the recursions, they have different peg orderings to cause different types of moves (for example, from peg 2 to peg 3 instead of peg 1 to peg 2)

[aikiart]

Fbody,

Thank you for your reply.
What seems to happen is that when the function is called again in line 10 in the function snippet, that the condition if(num > 0) gets retested which calls the function on line 7 to be called again, which inturn will stop being called when num =0, which will cause it to exit yet again but then return back to the function for the next call, per your example of an unwinding swing.

Is this the right way to think about this?

Art

[Fbody]

What it's doing, if you look at the initial function call and the parameters for the function, is testing how many discs are left on the current peg.

As long as there is a disc left on the peg, it performs another recursion to move another disc off the peg. Once it detects that it has moved enough discs, it returns and the chain begins to unwind.

[aikiart]

thanks
Art