Towers of Hanoi

[PlaneGraph88]

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:doh: ) 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!

[bascule]

...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?

 

Non-recursive solutions in procedural languages and recursive solutions are practically identical as they are effectively two approaches to implementing the same algorithm and both are provably correct as the minimal solution (although the procedural solution is inelegant and harder to implement, even though it will lead to the same number of steps). This is covered extensively on the Wikipedia article:

 

http://en.wikipedia.org/wiki/Tower_of_Hanoi#Solution

[PlaneGraph88]

OK,bascule,you are right about what you're saying,but this has absolutely nothing to do with what I asked advice for.As you can easily see in my post,I am referring to the recursive solution,and my concern is about how to trace correctly and demystify the recursive procedure.I know the iterative algorithm that solves the problem and the difference between iteration and recursion well enough.Thanks anyway.

[bascule]

Recursion is often counterintuitive. I spend some time each day implementing recursive algorithms in functional languages and I often find myself mystified by my own solutions actually working. I've pretty much come to the opinion that functional programming is difficult to reason about and often involves too much magic.