Tower of Hanoi: Recursive Algorithm

Question

I am a Computer Science student, and as such I have no problem whatsoever understanding recursion. However, 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

This doesn't answer your question, but I always found the iterative solution to the Tower of Hanoi interesting (and easier to understand).

Answer 2

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 3

I agree this one isn't immediate when you first look at it, but it's fairly simple when you get down to it.

Base case: your tower is of size 1. So you can do it in one move, from source directly to dest.

Recursive case: your tower is of size n > 1. So you move the top tower of size n-1 to an extra peg (by), move the bottom "tower" of size 1 to the destination peg, and move the top tower from by to dest.

So with a simple case, you have a tower of height 2:

-
--   |    |

First step: move the top tower of 2-1 (=1) to the extra peg (the middle one, lets say).

--   -    |

Next: move the bottom disc to the destination:

|    -    --

And finally, move the top tower of (2-1)=1 to the destination.

          -
|    |    --

If you think about it, even if the tower were 3 or more, there will always be an empty extra peg, or a peg with all larger discs, for the recursion to use when swapping towers around.

Answer 4

The first recursive call moves all the pieces except the biggest one from source to by using dest as the auxilary pile. When done all the pieces except the biggest will lie on by and the biggest one is free. Now you can move the biggest one to dest and use another recursive call to move all the pieces from by to dest.

The recursive calls won't know anything about the biggest piece (i.e. they will ignore it), but that's ok because the recursive calls will only deal with the pieces that are smaller and thus can be moved onto and off the biggest piece freely.

Answer 5

There's a good explanation of the recursive Hanoi implementation at http://www.cs.cmu.edu/~cburch/survey/recurse/hanoiimpl.html.

Summary is, if you want to move the bottom plate from stick A to stick B, you first have to move all the smaller plates on top of it from A to C. The second recursive call is then to move the plates you moved to C back onto B after your base case moved the single large plate from A to B.

Answer 6

It's simple. Suppose you want to move from A to C

if there's only one disk, just move it.

If there's more than one disk, do

• move all disks (n-1 disks), except the bottom one from A to B
• move the bottom disk from A to C
• move the n-1 disks from the first step from A to C

Keep in mind that, when moving the n-1 disks, the nth won't be a problem at all (once it is bigger than all the others)

Note that moving the n-1 disks recurs on the same problem again, until n-1 = 1, in which case you'll be on the first if (where you should just move it).

Answer 7

As a CS student, you might have heard about Mathematical induction. The recursive solution of Tower of Hanoi works analogously - only different part is to really get not lost with B and C as were the full tower ends up.

Answer 8

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) |          |          |
      |          |         _|_
   ___|___       |        __|__
  ____|____  ____|____  ____|____ (A -> 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)

Answer 9

I know this thread is a bit old but, "on - in this order). Then the body of the function might look like

Solve(N, Src, Aux, Dst) if N is 0 exit else Solve(N-1, Src, Dst, Aux) Move from Src to Dst Solve(N-1, Aux, Src, Dst) This actually serves as the definition of the function Solve. The function is recursive in that it calls itself repeatedly with decreasing values of N until a terminating condition (in our case N=0) has been met. To me the sheer simplicity of the solution is breathtaking. For N=3 it translates into Move from Src to Dst Move from Src to Aux Move from Dst to Aux Move from Src to Dst Move from Aux to Src Move from Aux to Dst Move from Src to Dst Of course "Move" means moving the topmost disk. For N=4 we get the following sequence Move from Src to Aux Move from Src to Dst Move from Aux to Dst Move from Src to Aux Move from Dst to Src Move from Dst to Aux Move from Src to Aux Move from Src to Dst Move from Aux to Dst Move from Aux to Src Move from Dst to Src Move from Aux to Dst Move from Src to Aux Move from Src to Dst Move from Aux to Dst "

http://www.cut-the-knot.org/recurrence/hanoi.shtml

Okay...I don't understand how when N=3 it outputs Move from Src to Dst

and when N= 4 it outputs Move from Src to Aux,

I understand that the solution requires that, but I don't understand how in the program changing N changes the first output. Why doesn't it always output "Move from Src to Dst"?

For n=2 it would be Move Src to Aux. Move Src to Dest. Move Aux to Dest.

but I don't understand how that program would output that?? tHanks.

I DO Understand that If the number of disks is EVEN, the first move is Src to Aux. ELSE the first move is Src to Dst.

so if you simply reiterate that, you've failed to answer the question.

The question is how does the program KNOW that even is src to aux and odd is src to dst for the opening move? ? I don't see any distinguishing feature from the program that indicates odd v even.