Tower of Hanoi: Recursive Algorithm

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.

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)

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.

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.

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.

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

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.

This python3 example uses a recursive solution:

# Hanoi towers puzzle
# for each n, you have to move n-1 disks off the n disk onto another peg
# then you move the n disk to a free peg
# then you move the n-1 disks on the other peg back onto the n disk

def hanoi(n):
    if n == 1:
        return 1
    else:
        return hanoi(n-1) + 1 + hanoi(n-1)


for i in range(1, 11):
    print(f"n={i}, moves={hanoi(i)}")

Output:

n=1, moves=1
n=2, moves=3
n=3, moves=7
n=4, moves=15
n=5, moves=31
n=6, moves=63
n=7, moves=127
n=8, moves=255
n=9, moves=511
n=10, moves=1023

But of course the most efficient way to work out how many moves is to realise that the answers are always 1 less than 2^n. So the mathematical solution is 2^n - 1

Just saw this video today: Recursion 'Super Power' (in Python) - Computerphile and I think we should definitely have Professor Thorsten Altenkirch's code in here as its a very beautiful and elegant piece of recursion code and its not always that we have a quality video to show in an answer.

def move(f,t) : 
    print("move disc from {} to {}!".format(f,t))

def hanoi(n,f,h,t) : 
    if n==0 : 
        pass
    else :
        hanoi(n-1,f,t,h)
        move(f,t)
        hanoi(n-1,h,f,t)

our hanoi function has 4 parameters:

• n: number of discs
• f: origin where discs are (from)
• h: intermediate step 'via' (helper)
• t: final position where we want the discs to be in the end (target)

>>> hanoi(4,"A","B","C")
move disc from A to B!
move disc from A to C!
move disc from B to C!
move disc from A to B!
move disc from C to A!
move disc from C to B!
move disc from A to B!
move disc from A to C!
move disc from B to C!
move disc from B to A!
move disc from C to A!
move disc from B to C!
move disc from A to B!
move disc from A to C!
move disc from B to C!

I made a small change to the code here, if you look at the output you can see the small parts pattern are repeating in the parent nodes (Think of it as fractal images)

def moveTower(height,fromPole, toPole, withPole, ar = ''):
    if height >= 1:
        print( "    "*(3-height), "moveTower:", height, fromPole, toPole, ar )
        moveTower(height-1,fromPole,withPole,toPole)
        moveDisk(fromPole,toPole,height)
        moveTower(height-1,withPole,toPole,fromPole, '*')
    #print(withPole)

def moveDisk(fp,tp,height):
    print("    "*(4-height), "moving disk", "~"*(height), "from",fp,"to",tp)


moveTower(3,"A","B","C")

And the output is:

 moveTower: 3 A B 
     moveTower: 2 A C 
         moveTower: 1 A B 
             moving disk ~ from A to B
         moving disk ~~ from A to C
         moveTower: 1 B C *
             moving disk ~ from B to C
     moving disk ~~~ from A to B
     moveTower: 2 C B *
         moveTower: 1 C A 
             moving disk ~ from C to A
         moving disk ~~ from C to B
         moveTower: 1 A B *
             moving disk ~ from A to B

This is code in C++ for Tower of Hanoi, which is recursively called.

#include <iostream>
void toh(int n, char A, char B, char C) {
    if(n == 1) {
        std::cout << "Move Disc 1 from " << A << " to " << C << std::endl;
        return;
    }
    toh(n-1, A, C, B);
    std::cout << "Move Disc " << n << " from " << A << " to " << C <<std::endl;
    toh(n-1, B, A, C);
}
int main() {
    int numberOfDisc;
    char A = 'A', B = 'B', C = 'C';
    std::cout << "Enter the number of disc: ";
    std::cin >> numberOfDisc;
    toh(numberOfDisc,  A, B, C);
    return 0;
}

I highly recommend this video which illustrates the recursion for this problem in a very understandable way.

The key is to understand the repeating pattern in the solution. The problem can be divided into three main sub-problems. Assuming you have n disks that they are placed at rod A. The target rod is C, and you have B as an intermediate.

Main problem; move n disks from rod A to rod C by using rod B.

1. Move n-1 disks from rod A to rod B by using rod C.
2. Move the last disk from rod A to rod C.
3. Move n-1 disks from rod B to rod C by using rod A.

Sub-problems 1 and 3 are actually solved within the same problem division you see above. Lets take sub problem 1.

Sub-problem 1; move n-1 disks from rod A to rod B by using rod C.

1. Move n-2 disks from rod A to rod C by using rod B.
2. Move the last disk from rod A to rod B.
3. Move n-2 disks from rod C to rod B by using rod A.

We solve the sub-problem in the same way we solve the main-problem. Our base case will be when the number of disks are equal to 1 then we move it from one rod to target one, that's it.

Writing down these steps will help tremendously.

I actually found a very good explanation for this at https://helloml.org/tower-of-hanoi-recursion/. I recommend you to check it out.

In this article, they have mentioned the steps to solve this problem.

Steps to solve the Tower of Hanoi Problem:

1. Move 'n-1' disks recursively from the source rod to the auxiliary rod.
2. Move the nth disc from source rod to destination rod.
3. Move 'n-1' disks recursively from the auxiliary rod to the destination rod.

It considers a case of three disks and explains the algorithm with a set of images.

Tower (N,source,aux.dest):

1.  

   if N =1 Then
      Write : Source -> dest
      return
   end of if
   

2. move N-1 disk from peg source to peg aux

   call Tower (N-1, source, dest, aux)
   

3. write source -> dest

4. move N-1 disks from peg aux to peg dest

   call Tower (N-1, source, dest, aux)
   

5. return

def Hanoi(n, A, B, C):
    if(n==1): print "move plates to empty peg"
    else:
       Hanoi(n-1, A, B, C)
       print "move"+str(n)+" to peg "+C
       Hanoi(n-1, B, C, A)