# Java recursion – Towers Of Hanoi

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
```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:

```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
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
```

Last updated on June 4, 2017.