Python Program to Implement Tower of Hanoi Using Recursion

Don’t stop learning now. Get hold of all the important Java fundamentals with the Simple java program example guide and practice well.

Recursion in Python:

The Oxford English Dictionary defines recursion as the repeated use of a recursive technique or term.

When a function calls itself repeatedly until it meets a stated stopping condition, this is referred to as recursion. This type of function is known as a recursive function.

The technique of explaining an action in terms of itself is known as recursion.

Use of Recursion:

In general, recursive code is shorter and easier to write than iterative code. When loops are built or interpreted, they are generally transformed into recursive functions. Recursion is most useful for activities that can be broken down into smaller subtasks.

Format of Recursive Function:

A recursive function is made up of two major components:

Base Case: The base case is where all further calls to the same function end, implying that no additional recursive calls are made.
Recursive Case: In the recursive case, the function calls itself till it reaches the base case.
The answer to the primary problem is represented in terms of lesser problems until the smallest problem meets the base case in a recursive function.

Tower of Hanoi:

It is a mathematical puzzle game in which three identical rods and n discs of varying sizes are used. In the first rod, the discs are positioned so that the largest disc is at the bottom and the smallest is at the top. To complete the puzzle, put the discs in the same order in the final rod via the middle rod.

Rules of Towers of Hanoi:

At any given time, only one disc can be transferred.
Each move requires taking the uppermost disc from one of the stacks and placing it on top of another, i.e. a disc can only be moved if it is the uppermost disc on a stack.
A larger disc may not be stacked on top of a smaller disc.

Examples:

Example1:

Input:

given number of disks = 3

Output:

Move disk [1] from rod [ A ] to rod { C }
Move disk [2] from rod [ A ] to rod { B }
Move disk [1] from rod [ C ] to rod { B }
Move disk [3] from rod [ A ] to rod { C }
Move disk [1] from rod [ B ] to rod { A }
Move disk [2] from rod [ B ] to rod { C }
Move disk [1] from rod [ A ] to rod { C }

Example2:

Input:

given number of disks = 4

Output:

Move disk [1] from rod [ A ] to rod { B }
Move disk [2] from rod [ A ] to rod { C }
Move disk [1] from rod [ B ] to rod { C }
Move disk [3] from rod [ A ] to rod { B }
Move disk [1] from rod [ C ] to rod { A }
Move disk [2] from rod [ C ] to rod { B }
Move disk [1] from rod [ A ] to rod { B }
Move disk [4] from rod [ A ] to rod { C }
Move disk [1] from rod [ B ] to rod { C }
Move disk [2] from rod [ B ] to rod { A }
Move disk [1] from rod [ C ] to rod { A }
Move disk [3] from rod [ B ] to rod { C }
Move disk [1] from rod [ A ] to rod { B }
Move disk [2] from rod [ A ] to rod { C }
Move disk [1] from rod [ B ] to rod { C }

Program to Implement Tower of Hanoi Using Recursion in Python

Using Recursion(Static Input)
Using Recursion(User Input)

1)Using Recursion(Static Input)

Approach:

Give the number of discs as static input and store it in a variable.
Create a recursive function called tower of Hanoi and pass two arguments: the number of discs n and the names of the rods such as source, aux, and destination.
When the number of discs is one, we can define the base case. Simply move the single disc from source to target and return in this scenario.
Now, use the target as the auxiliary to shift the remaining n-1 discs from source to auxiliary.
The remaining 1 disc then moves from source to target.
Use the source as the auxiliary to move the n-1 discs on the auxiliary to the target.

Below is the implementation:

# Create a recursive function called tower of Hanoi and pass two arguments:
# the number of discs n and the names of the rods
# such as source, aux, and destination.


def Towers_Of_Hanoi(numdisks, frm_disc, to_disc, aux_disc):
  # When the number of discs is one, we can define the base case. Simply move the
  # single disc from source to target and return in this scenario.
    if numdisks == 1:
        print("Move disk [1] from rod [",
              frm_disc, "] to rod {", to_disc, '}')
        return
    # Now, use the target as the auxiliary to
    # shift the remaining n-1 discs from source to auxiliary.
    Towers_Of_Hanoi(numdisks-1, frm_disc, aux_disc, to_disc)
    # The remaining 1 disc then moves from source to target.

    # Use the source as the auxiliary to move the n-1 discs on the auxiliary to the target.
    print("Move disk ["+str(numdisks) + "] from rod [",
          str(frm_disc)+" ] to rod {", to_disc, '}')
    Towers_Of_Hanoi(numdisks-1, aux_disc, to_disc, frm_disc)


# Give the number of discs as static input and store it in a variable.
numdisks = 4
# passing the given number of disks as argument to the towers of hanoi recursive function .
Towers_Of_Hanoi(numdisks, 'A', 'C', 'B')

Output:

Move disk [1] from rod [ A ] to rod { B }
Move disk [2] from rod [ A ] to rod { C }
Move disk [1] from rod [ B ] to rod { C }
Move disk [3] from rod [ A ] to rod { B }
Move disk [1] from rod [ C ] to rod { A }
Move disk [2] from rod [ C ] to rod { B }
Move disk [1] from rod [ A ] to rod { B }
Move disk [4] from rod [ A ] to rod { C }
Move disk [1] from rod [ B ] to rod { C }
Move disk [2] from rod [ B ] to rod { A }
Move disk [1] from rod [ C ] to rod { A }
Move disk [3] from rod [ B ] to rod { C }
Move disk [1] from rod [ A ] to rod { B }
Move disk [2] from rod [ A ] to rod { C }
Move disk [1] from rod [ B ] to rod { C }

2)Using Recursion(User Input)

Approach:

Give the number of discs as user input using the int(input()) function which converts the string to an integer.
Store it in a variable.
Create a recursive function called tower of Hanoi and pass two arguments: the number of discs n and the names of the rods such as source, aux, and destination.
When the number of discs is one, we can define the base case. Simply move the single disc from source to target and return in this scenario.
Now, use the target as the auxiliary to shift the remaining n-1 discs from source to auxiliary.
The remaining 1 disc then moves from source to target.
Use the source as the auxiliary to move the n-1 discs on the auxiliary to the target.

Below is the implementation:

# Create a recursive function called tower of Hanoi and pass two arguments:
# the number of discs n and the names of the rods
# such as source, aux, and destination.


def Towers_Of_Hanoi(numdisks, frm_disc, to_disc, aux_disc):
  # When the number of discs is one, we can define the base case. Simply move the
  # single disc from source to target and return in this scenario.
    if numdisks == 1:
        print("Move disk [1] from rod [",
              frm_disc, "] to rod {", to_disc, '}')
        return
    # Now, use the target as the auxiliary to
    # shift the remaining n-1 discs from source to auxiliary.
    Towers_Of_Hanoi(numdisks-1, frm_disc, aux_disc, to_disc)
    # The remaining 1 disc then moves from source to target.

    # Use the source as the auxiliary to move the n-1 discs on the auxiliary to the target.
    print("Move disk ["+str(numdisks) + "] from rod [",
          str(frm_disc)+" ] to rod {", to_disc, '}')
    Towers_Of_Hanoi(numdisks-1, aux_disc, to_disc, frm_disc)


# Give the number of discs as user input using
# the int(input()) function which converts the string to an integer.
# Store it in a variable.
numdisks = int(input('Enter some random number of disks = '))
# passing the given number of disks as argument to the towers of hanoi recursive function .
Towers_Of_Hanoi(numdisks, 'A', 'C', 'B')

Output:

Enter some random number of disks = 5
Move disk [1] from rod [ A ] to rod { C }
Move disk [2] from rod [ A ] to rod { B }
Move disk [1] from rod [ C ] to rod { B }
Move disk [3] from rod [ A ] to rod { C }
Move disk [1] from rod [ B ] to rod { A }
Move disk [2] from rod [ B ] to rod { C }
Move disk [1] from rod [ A ] to rod { C }
Move disk [4] from rod [ A ] to rod { B }
Move disk [1] from rod [ C ] to rod { B }
Move disk [2] from rod [ C ] to rod { A }
Move disk [1] from rod [ B ] to rod { A }
Move disk [3] from rod [ C ] to rod { B }
Move disk [1] from rod [ A ] to rod { C }
Move disk [2] from rod [ A ] to rod { B }
Move disk [1] from rod [ C ] to rod { B }
Move disk [5] from rod [ A ] to rod { C }
Move disk [1] from rod [ B ] to rod { A }
Move disk [2] from rod [ B ] to rod { C }
Move disk [1] from rod [ A ] to rod { C }
Move disk [3] from rod [ B ] to rod { A }
Move disk [1] from rod [ C ] to rod { B }
Move disk [2] from rod [ C ] to rod { A }
Move disk [1] from rod [ B ] to rod { A }
Move disk [4] from rod [ B ] to rod { C }
Move disk [1] from rod [ A ] to rod { C }
Move disk [2] from rod [ A ] to rod { B }
Move disk [1] from rod [ C ] to rod { B }
Move disk [3] from rod [ A ] to rod { C }
Move disk [1] from rod [ B ] to rod { A }
Move disk [2] from rod [ B ] to rod { C }
Move disk [1] from rod [ A ] to rod { C }

It prints all the valid moves of the disks.

Related Programs: