Earlier in the tutorial Solution for find the N-th Fibonacci number, we have already known the methods that can be easily implemented with recursion and iteration. Today we will see a solution which demonstrates the power of recursion, and the iterative solution may not be a clearer method: **Towers of Hanoi**.

##### I. Problem

Our goal is to move the all disks from **place[1]** to **place[3]** using only one temporary **place[2]**. Remember that the smallest disc is at the top and the largest is at the bottom.

There are 3 rules need to be followed:

1- Move only **ONE** disk at a time.

2- A disk can only be moved if it is the **uppermost disk** of the tower.

3- A **larger** disc cannot be placed over a **smaller** one.

##### II. Practice

Let’s assume that we have to move a tower with n disks like the image below:

We will use this Recursive algorithm:

– If **n = 1**: Move that disc from** place[1]** to **place[3]**. Everything is done.

– When **n > 1**:

1. move **(n-1)** disks from **place[1]** to **place[2]** using **place[3]**.

2. move last disk from place[1] to place[3].

3. move **(n-1)** disks from **place[2]** to **place[3]** using **place[1]**.

Step 1. and step 3. use the same procedure.

##### III. Source code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
public class TowersOfHanoi { public static void moveTowers(int numberOfDisks, int source, int destination, int temp) { if (numberOfDisks == 1) { System.out.printf("\n%d -> %d", source, destination); return; } // recursion: // 1- move (numberOfDisks - 1) disks from source to temp using destination moveTowers(numberOfDisks - 1, source, temp, destination); // 2- move last disk from source to destination System.out.printf("\n%d -> %d", source, destination); // 3- move (numberOfDisks - 1) disks from temp to destination using source moveTowers(numberOfDisks - 1, temp, destination, source); } } |

And this is how to use in context:

1 2 3 4 5 6 7 8 9 10 11 |
public class MainApp { public static void main(String[] args) { int start = 1; int end = 3; int temp = 2; int totalDisks = 3; // number of disks TowersOfHanoi.moveTowers(totalDisks, start, end, temp); } } |

Run the code with number of Disks is 4, the result is:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
1 -> 2 1 -> 3 2 -> 3 1 -> 2 3 -> 1 3 -> 2 1 -> 2 1 -> 3 2 -> 3 2 -> 1 3 -> 1 2 -> 3 1 -> 2 1 -> 3 2 -> 3 |