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

And this is how to use in context:

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


Related Posts


Got Something To Say:

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

*