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


By grokonez | February 9, 2017.

Last updated on June 4, 2017.



Related Posts


Got Something To Say:

Your email address will not be published. Required fields are marked *

*