• Java
    • JAXB Tutorial
      • What is JAXB
      • JAXB Marshalling Example
      • JAXB UnMarshalling Example
  • Spring Tutorial
    • Spring Core Tutorial
    • Spring MVC Tutorial
      • Quick Start
        • Flow Diagram
        • Hello World Example
        • Form Handling Example
      • Handler Mapping
        • BeanNameUrlHandlerMapping
        • ControllerClassNameHandlerMapping
        • SimpleUrlHandlerMapping
      • Validation & Exception Handling
        • Validation+Annotations
        • Validation+ResourceBundle
        • @ExceptionHandler
        • @ControllerAdvice
        • Custom Exception Handling
      • Form Tag Library
        • Textbox Example
        • TextArea Example
        • Password Example
        • Dropdown Box Example
        • Checkboxes Example
        • Radiobuttons Example
        • HiddenValue Example
      • Misc
        • Change Config file name
    • Spring Boot Tutorial
  • Hibernate Tutorial
  • REST Tutorial
    • JAX-RS REST @PathParam Example
    • JAX-RS REST @QueryParam Example
    • JAX-RS REST @DefaultValue Example
    • JAX-RS REST @Context Example
    • JAX-RS REST @MatrixParam Example
    • JAX-RS REST @FormParam Example
    • JAX-RS REST @Produces Example
    • JAX-RS REST @Consumes Example
    • JAX-RS REST @Produces both XML and JSON Example
    • JAX-RS REST @Consumes both XML and JSON Example
  • Miscellaneous
    • JSON Parser
      • Read a JSON file
      • Write JSON object to File
      • Read / Write JSON using GSON
      • Java Object to JSON using JAXB
    • CSV Parser
      • Read / Write CSV file
      • Read/Parse/Write CSV File – OpenCSV
      • Export data into a CSV File
      • CsvToBean and BeanToCsv – OpenCSV

JavaInterviewPoint

Java Development Tutorials

Tower of Hanoi in Java Using Recursion

August 26, 2016 by javainterviewpoint Leave a Comment

What is Tower of Hanoi ?

Tower of Hanoi is also called as Tower of Brahma or Lucas Tower. It is one of the most popular problem which makes you understand the power of recursion.  Tower of Hanoi is a mathematical puzzle which consist of 3 poles and number of discs of different sizes. Initially all the discs will be places in the single pole with the largest disc at the bottom and smallest on the top. We need to move all the disc from the first pole to the third pole with the smallest disc at the top and the largest at the bottom under the below conditions

  1. Only one disc can be moved at a time.
  2. Larger disc cannot be placed on a smaller disc.

Tower Of HanoiTower of Hanoi algorithm

We will be using Java Recursion to solve this problem and the below step will be performed. Let’s assume there are ‘n’ discs and 3 poles (pole1, pole2, pole3)

Step 1: Move (n-1) discs from pole1 to pole2
Step 2: Move the nth disc (last disc) from pole1 to pole3.
Step 3: Now move the n-1 discs which is present in pole2 to pole3.

Step1 and Step3 will be recursive. Lets take a look into the below Java code, where we have implemented the Tower of Hanoi algorithm using recursion.

package com.javainterviewpoint;

import java.util.Scanner;

public class TowerOfHanoi
{
    public static void shift(int n, String startPole, String intermediatePole, String endPole)
    {
        if (n == 0)
        {
            return;
        }
        shift(n - 1, startPole, endPole, intermediatePole);
        System.out.println("Move \"" + n + "\" from " + startPole + " --> " + endPole);
        shift(n - 1, intermediatePole, startPole, endPole);
    }
    public static void main(String[] args)
    {
        System.out.print("Enter number of discs: ");
        Scanner scanner = new Scanner(System.in);
        int numberOfDiscs = scanner.nextInt();
        shift(numberOfDiscs, "Pole1", "Pole2", "Pole3");
    }
}

In our TowerOfHanoi class we have shift() method which will be recursively called. It takes up 4 parameters n(number of discs), startPole, intermediatePole, endPole are the three poles which will be used for swapping.

We will start the recursion by swapping the n-1 disc from the startPole to the intermediatePole, followed by moving the disc from intermediatePole to the endPole. This will be continued until n is equal to ‘zero’.

Output :

Enter number of discs: 5

Move “1” from Pole1 –> Pole3
Move “2” from Pole1 –> Pole2
Move “1” from Pole3 –> Pole2
Move “3” from Pole1 –> Pole3
Move “1” from Pole2 –> Pole1
Move “2” from Pole2 –> Pole3
Move “1” from Pole1 –> Pole3
Move “4” from Pole1 –> Pole2
Move “1” from Pole3 –> Pole2
Move “2” from Pole3 –> Pole1
Move “1” from Pole2 –> Pole1
Move “3” from Pole3 –> Pole2
Move “1” from Pole1 –> Pole3
Move “2” from Pole1 –> Pole2
Move “1” from Pole3 –> Pole2
Move “5” from Pole1 –> Pole3
Move “1” from Pole2 –> Pole1
Move “2” from Pole2 –> Pole3
Move “1” from Pole1 –> Pole3
Move “3” from Pole2 –> Pole1
Move “1” from Pole3 –> Pole2
Move “2” from Pole3 –> Pole1
Move “1” from Pole2 –> Pole1
Move “4” from Pole2 –> Pole3
Move “1” from Pole1 –> Pole3
Move “2” from Pole1 –> Pole2
Move “1” from Pole3 –> Pole2
Move “3” from Pole1 –> Pole3
Move “1” from Pole2 –> Pole1
Move “2” from Pole2 –> Pole3
Move “1” from Pole1 –> Pole3

Other interesting articles which you may like …

  • JVM Architecture – Understanding JVM Internals
  • Object and Object Class in Java
  • Difference between JDK, JRE and JVM
  • Components of Java Development Kit (JDK)
  • What is a Class in Java with Example
  • How to open .class file in Java
  • How to Set Classpath for Java in Windows
  • Difference Between ClassNotFoundException Vs NoClassDefFoundError In Java
  • How HashMap works in Java
  • How to make a class Immutable in Java
  • Polymorphism in Java – Method Overloading and Overriding
  • Types of polymorphism in java
  • Types of Inheritance in Java
  • Why Java does not supports Multiple Inheritance – Diamond Problem?

Filed Under: Core Java, Java, Java Interview Tagged With: Recursion, Tower of Hanoi

Leave a Reply Cancel reply

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Java Basics

  • JVM Architecture
  • Object in Java
  • Class in Java
  • How to Set Classpath for Java in Windows
  • Components of JDK
  • Decompiling a class file
  • Use of Class.forName in java
  • Use Class.forName in SQL JDBC

Oops Concepts

  • Inheritance in Java
  • Types of Inheritance in Java
  • Single Inheritance in Java
  • Multiple Inheritance in Java
  • Multilevel Inheritance in Java
  • Hierarchical Inheritance in Java
  • Hybrid Inheritance in Java
  • Polymorphism in Java – Method Overloading and Overriding
  • Types of Polymorphism in java
  • Method Overriding in Java
  • Can we Overload static methods in Java
  • Can we Override static methods in Java
  • Java Constructor Overloading
  • Java Method Overloading Example
  • Encapsulation in Java with Example
  • Constructor in Java
  • Constructor in an Interface?
  • Parameterized Constructor in Java
  • Constructor Chaining with example
  • What is the use of a Private Constructors in Java
  • Interface in Java
  • What is Marker Interface
  • Abstract Class in Java

Java Keywords

  • Java this keyword
  • Java super keyword
  • Final Keyword in Java
  • static Keyword in Java
  • Static Import
  • Transient Keyword

Miscellaneous

  • newInstance() method
  • How does Hashmap works internally in Java
  • Java Ternary operator
  • How System.out.println() really work?
  • Autoboxing and Unboxing Examples
  • Serialization and Deserialization in Java with Example
  • Generate SerialVersionUID in Java
  • How to make a class Immutable in Java
  • Differences betwen HashMap and Hashtable
  • Difference between Enumeration and Iterator ?
  • Difference between fail-fast and fail-safe Iterator
  • Difference Between Interface and Abstract Class in Java
  • Difference between equals() and ==
  • Sort Objects in a ArrayList using Java Comparable Interface
  • Sort Objects in a ArrayList using Java Comparator

Follow

  • Coding Utils

Useful Links

  • Spring 4.1.x Documentation
  • Spring 3.2.x Documentation
  • Spring 2.5.x Documentation
  • Java 6 API
  • Java 7 API
  • Java 8 API
  • Java EE 5 Tutorial
  • Java EE 6 Tutorial
  • Java EE 7 Tutorial
  • Maven Repository
  • Hibernate ORM

About JavaInterviewPoint

javainterviewpoint.com is a tech blog dedicated to all Java/J2EE developers and Web Developers. We publish useful tutorials on Java, J2EE and all latest frameworks.

All examples and tutorials posted here are very well tested in our development environment.

Connect with us on Facebook | Privacy Policy | Sitemap

Copyright ©2023 · Java Interview Point - All Rights Are Reserved ·