Cannot make sense of my lecturers recursive algorithm for the Towers 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 is meant to work, can anyone make sense of this?

Sorry for being vague in my description here, it's just my understanding of what's happening is pretty vague too - I have no clue what the printf line is doing which seems pivotal to the whole function.

dup http://stackoverflow.com/questions/1223305/tower-of-hanoi-recursive-algorithm — pyrometer, Oct 09 '12 at 04:53

score 5 · Answer 1 · answered Apr 11 '11 at 18:50

The recursive algorithm is broken down into three steps:

Move all discs but one to the "spare" peg
Move the last disc to the destination peg
Move all discs but one (those from step 1) from the spare peg to the destination peg

Thus all discs have been moved to the destination peg.

Steps 1 and 3 are the two recursive move(k-1, ...) calls in the pseudocode. Step 2 is modelled by the printf.

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

In effect, this pseudocode does not implement an algorithm for moving the pegs; it's an algorithm for providing instructions to a human, if you will.

Cannot make sense of my lecturers recursive algorithm for the Towers of Hanoi

1 Answers1