If you’ve taken courses in computer sciences, you probably know the Tower Of Hanoi algorithm. The task is to move a tower of discs from the source rod the the destination using an auxiliary rod. Each disc should be placed on a bigger one all the time.

The solution is to move all discs on top of the biggest one to the auxiliary rod, then move the biggest disc to the destination rod and then move all the rest to the destination (according to the rules of course, and one disc at a time).

## The Recursive (and Naive) Solution

The function that moves `n`

discs from `src`

to `dst`

using `aux`

looks like:

function moveDiscs(n, src, dst, aux){ if (n > 1) moveDiscs(n-1, src, aux, dst); print("Move from " + src + " to " + dst); if (n>1) moveDiscs(n-1, aux, dst, src); }

We’ll use that function later to prove that the non-recursive algorithm does the same.

## The Iterative Solution

A naive iterative solution is to use a binary search and find for each move of a disc, the parameters passed to `moveDiscs`

when `n=1`

. This is crazy! We don’t want time complexity `o(n)`

just to move the first disc.

Let’s look at a better solution:

Repeat the 3 steps in table 1 until all discs are moved, depending on the value of `n`

:

__Table 1:__

If `n` is even | If `n` is odd |
---|---|

perform a legal move between `src` and `aux` | perform a legal move between `src` and `dst` |

perform a legal move between `src` and `dst` | perform a legal move between `src` and `aux` |

perform a legal move between `aux` and `dst` | perform a legal move between `aux` and `dst` |

Note: perform no more step after all discs have been moved to the destination.

### Proof

For `n`

= 1, just move a disc from `src`

to `dst`

For `n`

= 2, take a look at the recursive function.

For `n`

≥ 3:

The total number of moves is 2^{n} – 1

Let’s assume our algorithm works for any natural number `n`

and prove for `n`

+1:

#### Steps 1 thru 2^{n} – 1

Let’s look at the first call to `moveDiscs`

inside itself:

moveDiscs(n-1, src, aux, dst); // Remember that we prove for `n+1`, so `n-1` in the function actually means `n`

Let’s look how it is performed:

Per our assumption, the sequence for steps 1 thru 2^{n} – 1 is

If `n` is even | If `n` is odd |
---|---|

perform a legal move between `src` and `dst` | perform a legal move between `src` and `aux` |

perform a legal move between `src` and `aux` | perform a legal move between `src` and `dst` |

perform a legal move between `aux` and `dst` | perform a legal move between `aux` and `dst` |

Because if `n`

is odd, `n+1`

is even and vice versa, we get that the first steps are performed correctly by the iterative algorithm

#### Step 2^{n}

This is when we move a disc from `src`

to `dst`

If `n`

is even, 2^{n}≡1 mod 3, thus it matches step 1 in *Table 1* for odd `n+1`

.

If `n`

is odd, 2^{n}≡2 mod 3, thus it matches step 2 in *Table 1* for even `n+1`

.

Thus, our iterative algorithm is still correct.

#### Steps 2^{n} + 1 Thru 2^{n+1} – 1

Those steps are performed by the second call to `moveDiscs`

inside itself:

moveDiscs(n-1, aux, dst, src); // Remember that we prove for `n+1`, so `n-1` in the function actually means `n`

If `n` is even | If `n` is odd |
---|---|

perform a legal move between `aux` and `src` (step 2 for odd `n+1` ) | perform a legal move between `aux` and `dst` (step 3 for even `n+1` ) |

perform a legal move between `aux` and `dst` (step 3 for odd `n+1` ) | perform a legal move between `src` and `aux` (step 1 for even `n+1` ) |

perform a legal move between `src` and `dst` (step 1 for odd `n+1` ) | perform a legal move between `src` and `dst` step 2 for even `n+1` ) |

In this table we see the steps that follow step 2^{n}.

Thus, the algorithm works correctly for the last part, and thus our whole algorithm is correct.

You can now watch a working Hanoi animation here.