## Python Program – Tower of Hanoi

The **Tower of Hanoi** is a classic puzzle game consisting of three pegs and a number of disks of different sizes, which can slide onto any peg.

The puzzle starts with the disks in a neat stack in ascending order of size on one peg, the smallest at the top, thus making a conical shape. The objective of the puzzle is to move the entire stack to another peg.

And the movement of disks between the pegs must obey the following simple rules:

- Only one disk can be moved at a time.
- Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty peg.
- No disk may be placed on top of a smaller disk.

The puzzle is commonly used in computer science and programming as an example of a recursive function.

## Tower of Hanoi Program using Recursion

In the following program, we will use recursion technique to solve the Tower of Hanoi problem.

tower_of_hanoi() function has four parameters.

**n**– the number of disks.**from_rod**– The rod which has all the disks at the start.**to_rod**– The rod to which all the disks has to be moved.**aux_rod**– The auxiliary rod which can be used to place the disks temporarily.

**Python Program**

```
def tower_of_hanoi(n, from_rod, to_rod, aux_rod):
if n == 1:
print("Move disk 1 from rod", from_rod, "to rod", to_rod)
return
tower_of_hanoi(n-1, from_rod, aux_rod, to_rod)
print("Move disk", n, "from rod", from_rod, "to rod", to_rod)
tower_of_hanoi(n-1, aux_rod, to_rod, from_rod)
# Number of disks
n = 4
tower_of_hanoi(n, 'A', 'C', 'B')
```

Run Code Copy**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
```

## Summary

In this tutorial, we learned how to solve the problem of **Tower of Hanoi** using recursion, with examples.