I can’t understand what recursive algorithms of my lecturers are for the Tower of Hanoi

Question

The algorithm is as follows:

Algorithm move(k, from, to, spare) if k >0 then move(k−1, from, spare, to) printf ("move top disc from %d to %d\n", from, to) move(k−1, spare, to, from) 

k is the number of disks (http://en.wikipedia.org/wiki/Tower_of_Hanoi). I understand recursion, I just don’t understand how this should work, can anyone understand this?

Sorry for the nebula in my description here, just my understanding of what is happening is also rather vague - I don't know what the printf line does, which seems key to the whole function.

Answer 1

The recursive algorithm is divided into three stages:

• Move all but one drive to a spare mate
• Move last drive to destination
• Move all but one drive (from step 1) from the spare binding to the destination binding

Thus, all disks were transferred to the destination binding.

Steps 1 and 3 are two recursive calls to move(k-1, ...) in the pseudo-code. Step 2 is simulated by printf .

The point here is that steps 1 and 3 return more calls to move , and each call to move for which k > 0 prints exactly one line of commands with prinft . So what will happen is that this algorithm will print the steps you need to take to move the disks in detail, one by one.

In fact, this pseudo code does not implement the peg moving algorithm; it is an algorithm for providing instructions to a person if you do.