Towers of Hanoi

[wonder87]

Hi all!
As a person who has not a Computer Science degree(I am a poor web developer!),but having much desire to learn as much as I can about CS topics,I have a (maybe easy ) question about the recursive algorithm that solves the "Towers of Hanoi" puzzle.
I can understand that generally,having n discs and A,B,C pegs,the strategy is:
1.move (n-1) discs from A to B.
2.move nth disc from A to C.
3.move the (n-1) discs from B to C.Done!
but this is implemented in whatever procedural language with a function,and the one thing that changes,is the order of arguments.OK so far but how do we assure that algorithm does recursively the moves that must be done and not something else?In other words how to be sure that changing of passed arguments leads to the correct solution?Because of two recursive functions used(I have studied implementations in Pascal,C,Java so far),it was difficult for me to construct a tracetable,because at the point of second recursive function call,things get much complicated I think,due to the fact that on return of function call,first recursive function is encountered first and after that we go to second etc.
So is there any idea about how to construct a tracetable "safely",or at least how to trace the whole procedure?
I tried also to solve the problem with the physical moves of discs required,but I didn't manage to map this to the recursive function calls.And something maybe more elementary:in what sense do we have recursion in this problem/
Any help or resource would be appreciated.Thanks in advance!

[sarehu]

You assure that the algorithm works by proving it works. For recursive functions (and oftentimes, for things like while loops), you can prove the function works with the following sort of strategy:

1. Prove this fact: It works when n = 0.
2. Prove this fact for any positive integer "k": If it works when n = k-1, it works when n = k.

If you can prove these two facts, it means that the function works for any value of n that's greater than or equal to zero.

We can apply this reasoning to the Towers of Hanoi problem.

What does it mean for the function to "work"? If you run Hanoi(n, startTower, endTower) "working" means printing out instructions for moving blocks such that the top n blocks on startTower become located on endTower. Let's try to prove both statements 1 and 2 listed above.

Statement 1: Does it work when n = 0? Yes, it prints out nothing, right? Which is correct, because if you follow the instructions it prints out, you'll have successfully moved 0 blocks from startTower to endTower. So that proves Statement 1.

Statement 2: Assuming it works when n=k-1, does it work when n=k? We write instructions for moving the first k-1 blocks to the auxiliary tower (which works properly, we assume), and then we move the k'th block from the start tower to the end tower, and then we move the k-1 blocks from the auxiliary tower to the end tower (and so they end up on top of the k'th block). And thus we see that this causes the top k blocks to be moved to the endTower.

And that's it. We know it "works". That is, we know it moves the blocks to the end target, and that they end up in the right order.

What we _haven't_ shown (because I deliberately decided to leave this out) is that no two rocks are ever in reverse order on a pole. That's not hard to add, it just requires changing the definition of "works" to the following: Given that all the other rocks on all the poles are heavier than the top n rocks on the start pole, our function prints instructions for moving the top n rocks to the finish pole without reversing the order of any rocks. You only need a slight tweak to statement 2 to show this modified definition of "works".

The problem of tracing the excution of the program is slightly inconvenient because you need to keep track of stack frames. Say your hanoi function is the following:

// start and target are numbers 1, 2, or 3.  It happens that
// the xor operation (^) gets the auxiliary tower number
void hanoi(int n, int start, int target) {
  if (n != 0) {
    hanoi(n-1, start, start ^ target);
    println("Move rock from tower " + start + " to tower " + target);
    hanoi(n-1, start ^ target, target);
  }
}

Just to make things easy to describe, let me put some labels in the code to make things clear.

// start and target are numbers 1, 2, or 3.  It happens that
// the xor operation (^) gets the auxiliary tower number
void hanoi(int n, int start, int target) {
 A:
  if (n != 0) {
   B:
    hanoi(n-1, start, start ^ target);
   C:
    println("Move rock from tower " + start + " to tower " + target);
   D:
    hanoi(n-1, start ^ target, target);
  }
 E:
}

If I were to represent the current state of the program, it might look something like this. It lists each label at which you continue, once you return to that stack frame. In the bottom frame it just lists the current location in that frame.

C (n=5, start=1, target=2)
C (n=4, start=1, target=3)
E (n=3, start=1, target=2)
C (n=2, start=3, target=2)
D (n=1, start=3, target=1)

At this point, I just printed out "Move rock from tower 3 to tower 1." In the next step, I would be at the state:

C (n=5, start=1, target=2)
C (n=4, start=1, target=3)
E (n=3, start=1, target=2)
C (n=2, start=3, target=2)
E (n=1, start=3, target=1)
A (n=0, start=2, target=1)

Then, once the conditional fails:

C (n=5, start=1, target=2)
C (n=4, start=1, target=3)
E (n=3, start=1, target=2)
C (n=2, start=3, target=2)
E (n=1, start=3, target=1)
E (n=0, start=2, target=1)

When returning, you just chop off the bottom stack frame.

C (n=5, start=1, target=2)
C (n=4, start=1, target=3)
E (n=3, start=1, target=2)
C (n=2, start=3, target=2)
E (n=1, start=3, target=1)

C (n=5, start=1, target=2)
C (n=4, start=1, target=3)
E (n=3, start=1, target=2)
C (n=2, start=3, target=2)

These charts are neat looking, useful for visualizing the way a recursive function behaves, and map directly to the actual behavior of the code generated by the compiler. The way to know a recursive function works is by thinking about its behavior in terms of itself, by assuming that the recursive calls work. You can't use any "trace table" because the amount of memory used by an instance of the function is not a constant amount.

The stack frame tables I drew above are related to trace tables in that the rows of a trace table are just stack frame diagrams that have a single stack frame, that are all located at the same point in code.

Here's a neat optimization: Any time you see a row in the above diagrams with label E, you can just omit that row, because E is at the end of the function, and you would just return immediately anyway. Some compilers actually do this; it's known as "tail call elimination."

[wonder87]

Thanks very much for your reply sarehu.It is very descriptive.And you are absolutely right about using induction to prove the correctness of an algorithm,though I am not very skilled yet, to do this,in every algorithm I encounter,but I'll try it hard for sure!Thanks again!

[sarehu]

Yeah, "using" induction to prove the correctness of an algorithm, ever so formally, is a hassle. Thinking inductively (I mean recursively) is less-so.

When you have an algorithm with recursive calls, means asking, "assuming my algorithm works, does my algorithm work?" And then you don't have to worry about the mechanics of your sub-calls -- you just have to rely on the end behavior.

[sidatra79]

Hallo
have a look at my post here:

http://www.daniweb.com/forums/thread150700.html

I posted a working implementation of Hanoi Towers in c++ there.
U can see both the recursion base case and the recursion step there.

If u dont understand sth write what and will try to explain u.

[aashish.raina]

Hi
I read what u have said,,,What i could make out was u need to see how the peocedure
works.
1:Do a dry run on some input let say n=4 2 pow 4 -1 = 15 steps will be taken

 Plz handle the base cases i am a bit lazy :)


tower(peg_a,peg_b,peg_c,n)
 {
        tower(peg_a,peg_b,peg_c,n-1);    
        tower(peg_a,peg_c,peg_b,1);
        tower(peg_b,peg_c,peg_a,n-1);
 }

Now to understand this code

                                        tower(peg_a,peg_b,peg_c,n)

                                        Tower take 4 arguments

                                         when u shift the disk form a to b ten call Tower(a,b,c,n)
                                                                                           b to c Tower(b,c,a,n)
                                          Only think of the first 2 arg in function and n will be the numbe of disk transfered...

third arg will be whatever peg is left.....

Now dry run it u will get a better idea of what i am saying...

Try solving some recursive functions like fact,febonachi and dry run them that will be helpful...