Tower of Hanoi

[medosz]

I got this program. I am struggling to find out its logic. I am not sure how the recursion steps follow each other in this program and the other thing is that there are 3 different arguments but the program prints 5 different resoult with the line19. Could somebody help me to understand it please?

#include <iostream>

using namespace std;

void move(int, int, int, int);

int main(){
  int numberOfDisks{3};
  int peg1{1};
  int peg3{3};
  int peg2{2};
  
  move(numberOfDisks, peg1, peg3, peg2);
}

void move(int numberOfDisks, int peg1, int peg3, int peg2){
    if(numberOfDisks>0){
        move(numberOfDisks-1, peg1, peg2, peg3);
        cout << peg1 << "->" << peg3 << endl;
        move(numberOfDisks-1, peg2, peg3, peg1);
    }
}
    

[jonnin]

you call move. move calls itself, before the print. again, and again, ... until disks == 0 (assuming its correct and does not go negative or do anything weird).
when it reaches zero, it prints the last one it did, which is the 1 disk case. then it calls move for the 1 disk case again....

basically it hits line 18 and stops what it is doing and calls a function (so what that it happens to be itself, its the same as if it called foo(), it stops there until foo() ends, right?). Now in the new copy of the function it hits line 18 again.... do you see?

[medosz]

I assume the following happening, please let me know if it is wrong:

1.) When line 16 executes it gets the argument value but it does not print anything until the last recursion step executes. This value will be the last one to print.

2) In line 17 It checks if the value is valid.

3.) In line 18 "move" calls itself and gets the new arument value for the 4 int variables (it did not print anything until the last recursion executes.) Then it calls itself again in line 20 and it keep repeating it until the "numberOfDisk>0" because each recursive steps "numberOfDisk-1".

I was trying to do all steps on paper step by step but I only got the following printed out: "1->3" , "1->2", "2->3". I have not got for example "3->2".
I am afraid if I do not unterstand this there is no point to move forward.

[jonnin]

16 is just the function call. things happen here, but they are not what one normally thinks of as execution.

17 is the base case. to stop the recursion from going on forever, there has to be a way out. Its not 'validity' so much as 'when to quit'.

the order matters on 18.
if there are 3 disks, it calls 18 with 3,2,1,0 and then 0 goes away (base case does nothing), the 1 returns and prints then calls move with 1 to the other peg. That calls with 1, then 0, ... and eventually pops back out. that puts you back to 2 on the original call base case, which calls move (2) and goes thrugh 2,1,0 cases for the second set, that ends and pops back, then it is on the 3 case and calls move the second time with 3,2,1,0...

if you are new to this, I highly suggest you study a simpler example to start, like factorial generation. Two recursive calls when you don't seem to understand recursion may be too much to try to visualize.

a good way to see what is happening is to load up the code with a lot more print statements and run it, then you can see it in action.

[MikeyBoy]

a good way to see what is happening is to load up the code with a lot more print statements and run it, then you can see it in action.

Even better would be to use your debugger to step through the code line by line. The debugger is one of the most useful tools a programmer has, so it's worth actually using it :)

[jonnin]

you can try that. If you can follow what is happening, it will be very enlightening in the debugger. Its a good suggestion.

About line 16: you need to understand the idea of the call stack / system stack to really get how recursion works. The best way I can explain it is to say that recursion is conceptually just a loop with a hidden but very usable stack data structure available to it.

so as you trace it by hand, trace it as if you were pushing and popping a stack.
the other thing is this horrid example reused peg1 etc names. So sometimes peg1 is peg2, due to the parameter shuffles, which is why this is mind blowing to try to do in your head. You really should rewrite it to have source, destination, and intermediate pegs or names like that. it should be clear when you move from source to intermediate and from intermediate to destination easily -- that mashup is really hurting ME trying to understand it and I have a very good idea of what it should be doing.

Give me a little bit. Im at work and busy today, but I will try to help more in a bit.

[medosz]

Thank you for your help, I appreciate it. I was sitting on it all day trying to figure it out.

Yes, I am new to this. I only seen the factorial and the fibonacci examples. Those are much clearer, however factorial has only one recursion, n * factorial(n-1) The fibonacci has 2 recursions but in the same line, fibonacci(n-1) + fibonacci(n-2).

In this Tower of Hanoi the most confusing things are that there are 2 recursions in 2 different lines and there is a cout between them plus the reused variables. I will spend most of my time tomorrow as well and I think I am getting there with your help.

[salem c]

Better variable names would help. peg[123] is just word blindness while you're trying to figure out what each one means at every single step of the way.

#include <iostream>

using namespace std;

void move(int numberOfDisks, int from, int to, int temp);

int main(){
  int numberOfDisks{3};
  int from{1};
  int to{3};
  int temp{2};

  move(numberOfDisks, from, to, temp);
}

void move(int numberOfDisks, int from, int to, int temp){
    if(numberOfDisks>0){
        // Move the n-1 pile to the temp peg
        move(numberOfDisks-1, from, temp, to);
        // Move the largest current disk
        cout << "Moving " << numberOfDisks << " from " << from << "->" << to << endl;
        // Move the n-1 pile from the temp peg
        move(numberOfDisks-1, temp, to, from);
    }
}

[medosz]

Thank you. I upgraded it and now it shows the steps that the program does as it was suggested earlier.

#include <iostream>

using namespace std;

void move(int numberOfDisks, int from, int to, int temp);

int main(){
  int numberOfDisks{3};
  int from{1};
  int to{3};
  int temp{2};

  move(numberOfDisks, from, to, temp);
}

void move(int numberOfDisks, int from, int to, int temp){
    if(numberOfDisks>0){
        
        cout << "1.) from =" << from << endl;
        cout << "1.) to = " << to << endl;
        cout << "1.) temp = " << temp << endl;
        cout << "1.) nODisks= " << numberOfDisks<< endl << endl;
        
        // Move the n-1 pile to the temp peg
        move(numberOfDisks-1, from, temp, to);
        
        cout << "2.) from= " << from << endl;
        cout << "2.) to = " << to << endl;
        cout << "2.) temp = " << temp << endl;
        cout << "2.) nODisks= " << numberOfDisks<< endl << endl; 
        
        // Move the largest current disk
        cout << "Moving " << numberOfDisks << " from " 
          << from << "->" << to << endl << endl;
        // Move the n-1 pile from the temp peg
        move(numberOfDisks-1, temp, to, from);
        
        cout << "3.) from= " << from << endl;
        cout << "3.) to = " << to << endl;
        cout << "3.) temp = " << temp << endl;
        cout << "3.) nODisks= " << numberOfDisks<< endl << endl;
    }   
}

[jonnin]

very nice!
Do you understand it now, though? If not, keep asking and poking at it. Once it clicks, this concept will help you if you need to deal with a tree traversal and other code. Recursion can do a lot in a couple of lines of code, saving you a lot of energy for certain types of problems.

[medosz]

It is clearer now, but there are few things I still can`t follow.
For example:

"Moving 2 from 1->2

1.) from =3
1.) to = 2
1.) temp = 1
1.) nODisks= 1"

I can`t see how the argument got the (temp, from, to). There is no such an argument in the program.

we have only:
(from, to, temp)
(from, temp, to)
(temp, to, from)

[jonnin]

so you are on like 33, printing moving 2 ...
and then hit line 36.
line 36 starts you right back in a new copy of the move function, and hits line 19.

temp, from, and to are passed into move. they are the parameters (line 16).
you pass them on 36.
it still re-arranges the parameters with the switcheroo.
at 36, you call move on {num,tmp, to, from} so when you hit 19 as I said above in the new copy of move, from is old tmp, to is to, and tmp is old from: tmp and from swapped!
That makes sense; it is how this problem is solved (by changing which peg is used as the intermediate storage and which has the disks on it).

[medosz]

I see so basically there is a copy of the line 25. Which means from= 1 temp=3, to = 2. Therefore when it hits line 36 it swaps the values and become temp = 1, to = 2, from = 3.

I am getting there. :) I think I need to focus on the order the steps the recursions make copies and execute the lines.

[dutch]

The best way to understand a recursive function is to NOT follow the recursive calls. You are allowed to assume that the recursive calls do what they are supposed to do. Only consider the first level of the call.

The functions's purpose is to print directions to move 'disks' disks from peg 'from' to peg 'to', using peg 'temp' as an extra peg, and following the rule of never putting a larger disk on a smaller disk. The starting position is all disks in proper order on peg 1. It's interesting to note that the actual disks themselves are not represented in the program. The number of disks on the pegs at each moment is not kept track of, only the total number of disks.

Reading just the top level of the function (assuming the recursive calls do what they are supposed to do):
* print directions to move all but the biggest disk from peg 1 to peg 2.
* print the direction to move the biggest disk from peg 1 to peg 3.
* print directions to move the disks from peg 2 to peg 3.

That will obviously give the correct answer, so the function is correct. This kind of description does not usually satisfy the beginner, but this point of view is the soul of recursion.

There are a couple of other details to consider. You need to ensure that there is at least one base case and that the recursive calls move towards the base case(s). Each recursive call should work on a reduced problem.

To satisfy your curiosity, we can follow one or two of the recursive calls in the same manner (assuming their recursive calls do what they're supposed to). The first recursive call will be handled in the same way as the initial call. All but the biggest disk is moved from 'from' (for that call) to the 'temp' peg, then the biggest disk is moved to the 'to' peg, then the disks that were moved to the 'temp' peg are moved to the 'to' peg. The next level call is handled the same way, until the base case (0 disks) is reached.

You can trace out the stack frames, etc, but the simplifying nature of recursion is that you don't need to consider those details. There's a kind of magic to it.

You can see the recursive structure of the problem by looking at the first few solutions:

Move 0 disks:
    do nothing
Move 1 disk:
    1->3
Move 2 disks:
    Move 1 disk:
        1->2
    1->3
    Move 1 disk:
        2->3
Move 3 disks:
    Move 2 disks:
        Move 1 disk:
            1->3
        1->2
        Move 1 disk:
            2->2
    1->3
    Move 2 disks:
        Move 1 disk:
            2->1
        2->3
        Move 1 disk:
            1->3
Move 4 disks:
    Move 3 disks:
        Move 2 disks:
            Move 1 disk:
                1->2
            1->3
            Move 1 disk:
                2->3
        1->2
        Move 2 disks:
            Move 1 disk:
                3->1
            3->2
            Move 1 disk:
                1->2
    1->3
    Move 3 disks:
        Move 2 disks:
            Move 1 disk:
                2->3
            2->1
            Move 1 disk:
                3->1
        2->3
        Move 2 disks:
            Move 1 disk:
                1->2
            1->3
            Move 1 disk:
                2->3