Tower of Hanoi: Recursive Algorithm

Question

Although I have no problem whatsoever understanding recursion, I can't seem to wrap my head around the recursive solution to the Tower of Hanoi problem. Here is the code from Wikipedia:

procedure Hanoi(n: integer; source, dest, by: char); Begin     if (n=1) then         writeln('Move the plate from ', source, ' to ', dest)     else begin         Hanoi(n-1, source, by, dest);         writeln('Move the plate from ', source, ' to ', dest);         Hanoi(n-1, by, dest, source);     end; End;

I understand the base case and the concept of breaking the problem into smaller pieces until you are able to move a single disk. However, I can't figure out how the two recursive calls in the non-base case work together. Perhaps someone can help me out? Thanks.

Answer 1

Actually, the section from where you took that code offers an explanation as well:

To move n discs from peg A to peg C:

1. move n−1 discs from A to B. This leaves disc #n alone on peg A
2. move disc #n from A to C
3. move n−1 discs from B to C so they sit on disc #n

It's pretty clear that you first have to remove n − 1 discs to get access to the nth one. And that you have to move them first to another peg than where you want the full tower to appear.

The code in your post has three arguments, besides the number of discs: A source peg, a destination peg and a temporary peg on which discs can be stored in between (where every disc with size n − 1 fits).

The recursion happens actually twice, there, once before the writeln, once after. The one before the writeln will move n − 1 discs onto the temporary peg, using the destination peg as temporary storage (the arguments in the recursive call are in different order). After that, the remaining disc will be moved to the destination peg and afterwards the second recursion compeltes the moving of the entire tower, by moving the n − 1 tower from the temp peg to the destination peg, above disc n.

Answer 2

a year ago i had i functional programming course and draw this illustration for the algorithm. hope it helps!

(0)  _|_         |          |     __|__        |          |    ___|___       |          |   ____|____  ____|____  ____|____  (1.1) |          |          |     __|__        |          |    ___|___      _|_         |   ____|____  ____|____  ____|____ (A -> B)  (1.2) |          |          |       |          |          |    ___|___      _|_       __|__   ____|____  ____|____  ____|____ (A -> C)  (1.3) |          |          |       |          |         _|_    ___|___       |        __|__   ____|____  ____|____  ____|____ (B -> C)    (2.1) |          |          |       |          |         _|_       |       ___|___     __|__   ____|____  ____|____  ____|____ (A -> B)    (3.1) |          |          |       |          |          |      _|_      ___|___     __|__   ____|____  ____|____  ____|____ (C -> A)  (3.2) |          |          |       |        __|__        |      _|_      ___|___       |   ____|____  ____|____  ____|____ (C -> B)  (3.3) |         _|_         |       |        __|__        |       |       ___|___       |   ____|____  ____|____  ____|____ (A -> B) 

The 3 rings problem has been splited to 2 2-rings problem (1.x and 3.x)