# Program for Tower of Hanoi

Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
1) Only one disk can be moved at a time.
2) Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
3) No disk may be placed on top of a smaller disk.

Approach :

```Take an example for 2 disks :
Let rod 1 = 'A', rod 2 = 'B', rod 3 = 'C'.

Step 1 : Shift first disk from 'A' to 'B'.
Step 2 : Shift second disk from 'A' to 'C'.
Step 3 : Shift first disk from 'B' to 'C'.

The pattern here is :
Shift 'n-1' disks from 'A' to 'B'.
Shift last disk from 'A' to 'C'.
Shift 'n-1' disks from 'B' to 'C'.

Image illustration for 3 disks : ```

Examples:

```Input : 2
Output : Disk 1 moved from A to B
Disk 2 moved from A to C
Disk 1 moved from B to C

Input : 3
Output : Disk 1 moved from A to C
Disk 2 moved from A to B
Disk 1 moved from C to B
Disk 3 moved from A to C
Disk 1 moved from B to A
Disk 2 moved from B to C
Disk 1 moved from A to C
```

## C++

 `// C++ recursive function to  ` `// solve tower of hanoi puzzle  ` `#include ` `using` `namespace` `std; ` ` `  `void` `towerOfHanoi(``int` `n, ``char` `from_rod, ` `                    ``char` `to_rod, ``char` `aux_rod)  ` `{  ` `    ``if` `(n == 1)  ` `    ``{  ` `        ``cout << ``"Move disk 1 from rod "` `<< from_rod <<  ` `                            ``" to rod "` `<< to_rod<

## C

 `#include ` ` `  `// C recursive function to solve tower of hanoi puzzle ` `void` `towerOfHanoi(``int` `n, ``char` `from_rod, ``char` `to_rod, ``char` `aux_rod) ` `{ ` `    ``if` `(n == 1) ` `    ``{ ` `        ``printf``(````" Move disk 1 from rod %c to rod %c"````, from_rod, to_rod); ` `        ``return``; ` `    ``} ` `    ``towerOfHanoi(n-1, from_rod, aux_rod, to_rod); ` `    ``printf``(````" Move disk %d from rod %c to rod %c"````, n, from_rod, to_rod); ` `    ``towerOfHanoi(n-1, aux_rod, to_rod, from_rod); ` `} ` ` `  `int` `main() ` `{ ` `    ``int` `n = 4; ``// Number of disks ` `    ``towerOfHanoi(n, ``'A'``, ``'C'``, ``'B'``);  ``// A, B and C are names of rods ` `    ``return` `0; ` `} `

## Java

 `// Java recursive program to solve tower of hanoi puzzle ` ` `  `class` `GFG ` `{ ` `    ``// Java recursive function to solve tower of hanoi puzzle ` `    ``static` `void` `towerOfHanoi(``int` `n, ``char` `from_rod, ``char` `to_rod, ``char` `aux_rod) ` `    ``{ ` `        ``if` `(n == ``1``) ` `        ``{ ` `            ``System.out.println(``"Move disk 1 from rod "` `+  from_rod + ``" to rod "` `+ to_rod); ` `            ``return``; ` `        ``} ` `        ``towerOfHanoi(n-``1``, from_rod, aux_rod, to_rod); ` `        ``System.out.println(``"Move disk "` `+ n + ``" from rod "` `+  from_rod + ``" to rod "` `+ to_rod); ` `        ``towerOfHanoi(n-``1``, aux_rod, to_rod, from_rod); ` `    ``} ` `     `  `    ``//  Driver method ` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `        ``int` `n = ``4``; ``// Number of disks ` `        ``towerOfHanoi(n, ``'A'``, ``'C'``, ``'B'``);  ``// A, B and C are names of rods ` `    ``} ` `} `

/div>

## Python

 `# Recursive Python function to solve tower of hanoi ` ` `  `def` `TowerOfHanoi(n , from_rod, to_rod, aux_rod): ` `    ``if` `n ``=``=` `1``: ` `        ``print` `"Move disk 1 from rod"``,from_rod,``"to rod"``,to_rod ` `        ``return` `    ``TowerOfHanoi(n``-``1``, from_rod, aux_rod, to_rod) ` `    ``print` `"Move disk"``,n,``"from rod"``,from_rod,``"to rod"``,to_rod ` `    ``TowerOfHanoi(n``-``1``, aux_rod, to_rod, from_rod) ` `         `  `# Driver code ` `n ``=` `4` `TowerOfHanoi(n, ``'A'``, ``'C'``, ``'B'``)  ` `# A, C, B are the name of rods ` ` `  `# Contributed By Harshit Agrawal `

## C#

 `// C# recursive program to solve  ` `// tower of hanoi puzzle ` `using` `System; ` ` `  `class` `geek ` `{ ` ` `  `    ``// C# recursive function to solve  ` `    ``// tower of hanoi puzzle ` `    ``static` `void` `towerOfHanoi(``int` `n, ``char` `from_rod,  ` `                             ``char` `to_rod, ``char` `aux_rod) ` `    ``{ ` `        ``if` `(n == 1) ` `        ``{ ` `            ``Console.WriteLine(``"Move disk 1 from rod "` `+ from_rod  ` `                                           ``+ ``" to rod "` `+ to_rod); ` `            ``return``; ` `        ``} ` `        ``towerOfHanoi(n-1, from_rod, aux_rod, to_rod); ` `        ``Console.WriteLine(``"Move disk "` `+ n + ``" from rod "`  `                          ``+ from_rod + ``" to rod "` `+ to_rod); ` `        ``towerOfHanoi(n-1, aux_rod, to_rod, from_rod); ` `    ``} ` `     `  `    ``// Driver method ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``// Number of disks ` `        ``int` `n = 4;  ` `         `  `        ``// A, B and C are names of rods ` `        ``towerOfHanoi(n, ``'A'``, ``'C'``, ``'B'``);  ` `    ``} ` `} ` ` `  `// This code is contributed by Sam007 `

## PHP

 ` `

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
```

For n disks, total 2n – 1 moves are required.

eg: For 4 disks 24 – 1 = 15 moves are required.

For n disks, total 2n-1 function calls are made.

eg: For 4 disks 24-1 = 8 function calls are made.
Related Articles

References:
http://en.wikipedia.org/wiki/Tower_of_Hanoi