[recursion] Tower of Hanoi: Recursive Algorithm

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.

The answer for the question, how does the program know, that even is "src" to "aux", and odd is "src" to "dst" for the opening move lies in the program. If you break down fist move with 4 discs, then this looks like this:

hanoi(4, "src", "aux", "dst");
if (disc > 0) {
    hanoi(3, 'src', 'dst', 'aux');
        if (disc > 0) {
            hanoi(2, 'src', 'aux', 'dst');
                if (disc > 0) {
                    hanoi(1, 'src', 'dst', 'aux');
                        if (disc > 0) {
                            hanoi(0, 'src', 'aux', 'dst');
                                END
                        document.writeln("Move disc" + 1 + "from" + Src + "to" + Aux);
                        hanoi(0, 'aux', 'src', 'dst');
                                END
                        }

also the first move with 4 disc(even) goes from Src to Aux.

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)

Suppose we want to move a disc from A to C through B then:

1. move a smaller disc to B.
2. move another disc to C.
3. move B to C.
4. move from A to B.
5. move all from C to A.

If you repeat all the above steps, the disc will transfer.

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

Think of it as a stack with the disks diameter being represented by integers (4,3,2,1) The first recursion call will be called 3 times and thus filling the run-time stack as follows

1. first call : 1. Second call : 2,1. and third call: 3,2,1.

After the first recursion ends, the contents of the run-time stack is popped to the middle pole from largest diameter to smallest (first in last out). Next, disk with diameter 4 is moved to the destination.

The second recursion call is the same as the first with the exception of moving the elements from the middle pole to destination.

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.

void TOH(int n, int a, int b){
        /*Assuming a as source stack numbered as 1, b as spare stack numbered as 2 and  c as target stack numbered as 3. So once we know values of a and b, we can determine c as there sum is a constant number (3+2+1=)6.
       */
int c = 6-a-b;
if(n==1){
    cout<<"Move from "<<a<<" to "<<b<<"\n";
}
else{
    // Move n-1 disks from 1st to 2nd stack. As we are not allowed to move more than one disks at a time, we do it by recursion. Breaking the problem into a simpler problem.
    TOH(n-1, a, c);
    // Move the last alone disk from 1st to 3rd stack.
    TOH(1, a, b);
    // Put n-1 disks from 2nd to 3rd stack. As we are not allowed to move more than one disks at a time, we do it by recursion. Breaking the problem into a simpler problem.        
    TOH(n-1, c, b);
}
}
int main() {

TOH(2, 1, 3);
cout<<"FINISHED                        \n";
TOH(3, 1, 3);
cout<<"FINISHED                        \n";
TOH(4, 1, 3);
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.

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

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.

As some of our friends suggested, I removed previous two answers and I consolidate here.

This gives you the clear understanding.

What the general algorithm is....

Algorithm:

solve(n,s,i,d) //solve n discs from s to d, s-source i-intermediate d-destination
{
    if(n==0)return;
    solve(n-1,s,d,i); // solve n-1 discs from s to i Note:recursive call, not just move
    move from s to d; // after moving n-1 discs from s to d, a left disc in s is moved to d
    solve(n-1,i,s,d); // we have left n-1 disc in 'i', so bringing it to from i to d (recursive call)
}

here is the working example Click here

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)

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

/** * */ package com.test.recursion;

/** * @author kamals1986 The Recursive algorithm for Tower of Hanoi Problem The * algorithm grows by power(2,n). */ public class TowerOfHanoi {

private static String SOURCE_PEG = "B";

private static String SPARE_PEG = "C";

private static String TARGET_PEG = "A";

public void listSteps(int n, String source, String target, String spare) {
    if (n == 1) {
        System.out.println("Please move from Peg " + source + "\tTo Peg\t"
                + target);
    } else {
        listSteps(n - 1, source, spare, target);
        listSteps(1, source, target, spare);
        listSteps(n - 1, spare, target, source);
    }
}

public static void main(String[] args) {
    long startTime = System.currentTimeMillis();
    new TowerOfHanoi().listSteps(18, SOURCE_PEG, TARGET_PEG, SPARE_PEG);

    long endTime = System.currentTimeMillis();

    System.out.println("Done in " + (endTime - startTime) / 1000
            + "\t seconds");
}

}

I feel the pain!

Although this is an old post, I think what one really needs to understand, is not the "move this to that" approach but that the answer involves using the side-effect of the recursion.

A invaluable help to me was the "The Little Schemer" which teaches one to think and write recursive functions.

However, this teaches the reader to use the results of the returned result in the next recursive call.

In the Tower of Hanoi, the answer is not in the returned result per se, but in the observation of the returned result.

The magic occurs in the succesive rearrangment of the function parameters.

Yes the problem is really in three parts:

• moving a smaller tower to the spare peg
• moving the last disc to the destination peg
• moving the remaining tower on the spare peg to the destination peg.

In Scheme:

(define (th n a b c)
    (if (zero? n) 'done
        (begin
           (th (- n 1) a c b)
           (display (list a c))
           (newline)
           (th (- n 1) b a c))))
(th 5 'source 'spare 'destination)

However it is the displaying of the function parameters which is the solution to the problem and crucially understanding the double tree like structure of the calls.

The solution also conveys the power of proof by induction and a warm glow to all programmers who have wrestled with conventional control structures.

Incidently, to solve the problem by hand is quite satisfying.

• count the number of discs
• if even, move the first disc to the spare peg, make next legal move (not involving the top disc). Then move the top disc to the destination peg, make the next legal move(nittd). Then move the top disc to the source peg, make the next legal move(nittd)...
• if odd, move the first disc to the destination peg, make the next legal move (not involving the top disc). Then move the top disc to the spare peg, make the next legal move(nittd). Then move the top disc to the source peg, make the next legal move(nittd)...

Best done by always holding the top disc with the same hand and always moving that hand in the same direction.

The final number of moves for n discs is 2^n - 1 the move n disc to destination is halfway through the process.

Lastly, it is funny how explaining a problem to a colleague, your wife/husband or even the dog (even it they not listening) can cement enlightenment.

I am trying to get recursion too.

I found a way i think,

i think of it like a chain of steps(the step isnt constant it may change depending on the previous node)

I have to figure out 2 things:

1. previous node
2. step kind
3. after the step what else before call(this is the argument for the next call

example

factorial

1,2,6,24,120 ......... or

1,2*(1),3*(2*1),4*(3*2*1,5*(4*3*2*1)

step=multiple by last node

after the step what i need to get to the next node,abstract 1

ok

function =

n*f(n-1) 

its 2 steps process
from a-->to step--->b

i hoped this help,just think about 2 thniks,not how to get from node to node,but node-->step-->node

node-->step is the body of the function step-->node is the arguments of the other function

bye:) hope i helped

After reading all these explanations I thought I'd weigh in with the method my professor used to explain the Towers of Hanoi recursive solution. Here is the algorithm again with n representing the number of rings, and A, B, C representing the pegs. The first parameter of the function is the number of rings, second parameter represents the source peg, the third is the destination peg, and fourth is the spare peg.

procedure Hanoi(n, A, B, C);
  if n == 1
    move ring n from peg A to peg B
  else
    Hanoi(n-1, A, C, B);
    move ring n-1 from A to C
    Hanoi(n-1, C, B, A);
end;

I was taught in graduate school to never to be ashamed to think small. So, let's look at this algorithm for n = 5. The question to ask yourself first is if I want to move the 5th ring from A to B, where are the other 4 rings? If the 5th ring occupies peg A and we want to move it to peg B, then the other 4 rings can only be on peg C. In the algorithm above the function Hanoi (n-1, A, C, B) is trying to move all those 4 other rings on to peg C, so ring 5 will be able to move from A to B. Following this algorithm we look at n = 4. If ring 4 will be moved from A to C, where are rings 3 and smaller? They can only be on peg B. Next, for n = 3, if ring 3 will be moved from A to B, where are rings 2 and 1? On peg C of course. If you continue to follow this pattern you can visualize what the recursive algorithm is doing. This approach differs from the novice's approach in that it looks at the last disk first and the first disk last.

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

There are three towers namely source tower, destination tower and helper tower. The source tower has all the disks and your target is to move all the disks to the destination tower and make sure in doing so, you never put a larger disk on top of a smaller disk. We can solve this problem using recursion in the steps below:

We have n numbers of disks on source tower

Base case: n=1 If there is only one disk in source tower, move it to destination tower.

Recursive case: n >1

• Move the top n-1 disks from from source tower to helper tower
• Move the only remaining, the nth disk(after step1) to destination tower
• Move the n-1 disks that are in helper tower now, to destination
  tower, using source tower as a helper.

Source code in Java:

private void towersOfHanoi(int n, char source, char destination, char helper) {
    //Base case, If there is only one disk move it direct from source to destination
    if(n==1){
        System.out.println("Move from "+source+" to "+destination);
    }
    else{
        //Step1: Move the top n-1 disks from source to helper
        towersOfHanoi(n-1, source, helper, destination);
        //Step2: Move the nth disk from source to destination
        System.out.println("Move from "+source+" to "+destination);
        /*Step3: Move the n-1 disks(those you moved from source to helper in step1) 
         * from helper to destination, using source(empty after step2) as helper
         */
        towersOfHanoi(n-1, helper, destination, source);
    }
}

Here goes the explanation. Look at the picture ->

By calling Movetower(3,a,b,c), you intend to move all the 3 discs from tower A to tower B. So the sequential calls are ->

1. Movetower(3,a,b,c)  // No Move needed
2. Movetower(2,a,c,b)  // No move needed
3. Movetower(1,a,b,c)  // Here is the time to move, move disc1 from a to b
4. Movetower(2,a,c,b)  // Returning to this call again, this is the time to move disc2 from a to c
5. Movetower(1,b,c,a)  // Again the time to move, this time disc1 from b to c
6. Movetower(3,a,b,c)  // Returning to this call again, this is the time to move disc3 from a to b
7. Movetower(2,c,b,a)  // Not the time to move
8. Movetower(1,c,a,b)  // Here is the time to move, move disc1 from c to a
9. Movetower(2,c,b,a)  // Returning to this call again, this is the time to move disc2 from c to b
10.Movetower(1,c,a,b)  // Here is the time to move, move disc1 from a to b

Hope it helps :)

For Animation : https://www.cs.cmu.edu/~cburch/survey/recurse/hanoiex.html

public static void hanoi(int number, String source, String aux, String dest)
{
    if (number == 1)
    {
        System.out.println(source + " - > "+dest);
    }
    else{
        hanoi(number -1, source, dest, aux);
        hanoi(1, source, aux, dest);
        hanoi(number -1, aux, source, dest);
    }
}

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.

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 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;
}

In simple sense the idea is to fill another tower among the three defined towers in the same order of discs as present without a larger disc overlapping a small disc at any time during the procedure.

Let 'A' , 'B' and 'C' be three towers. 'A' will be the tower containing 'n' discs initially. 'B' can be used as intermediate tower and 'C' is the target tower.

The algo is as follows:

1. Move n-1 discs from tower 'A' to 'B' using 'C'
2. Move a disc from 'A' to 'C'
3. Move n-1 discs from tower 'B' to 'C' using 'A'

The code is as follows in java:

public class TowerOfHanoi {

public void TOH(int n, int A , int B , int C){
    if (n>0){
        TOH(n-1,A,C,B);
        System.out.println("Move a disk from tower "+A +" to tower " + C);
        TOH(n-1,B,A,C);
    }
}

public static void main(String[] args) {
    new TowerOfHanoi().TOH(3, 1, 2, 3);
}   

}

Here is my solution code to Towers of Hanoi problem using recursion with golang. `package main

import "fmt"

func main() {
    toi(4, "src", "dest", "swap")
}

func toi(n int, from, to, swap string) {
    if n == 0 {
        return
    }
    if n == 1 {
        fmt.Printf("mov %v %v -> %v\n", n, from, to)
        return
    }
    toi(n-1, from, swap, to)
    fmt.Printf("mov %v %v -> %v\n", n, from, to)
    toi(n-1, swap, to, from)
}`

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!