# Tower of Hanoi Recursive Algorithm

The Tower of Hanoi is a puzzle, for which the goal is to move all disks from peg A to C, with the following rules for each move:

- Any pegs can be used to temporarily store a disk
- Disks can only be taken from the top of a stack
- Only a smaller disk can be place on top of a larger disk

An interactive version of the game can be found at mathisfun.com.

## Algorithm

A simple algorithm to find the optimal moves for the game is to use recursion. The idea is continuous reduction of the problem size by one.

For example, letâ€™s say we have N disks, moving from A to C. This can be reduced to moving N-1 disks to B, then after that we just have to move one bottom disk from A to C. Last step is to move N-1 disk from B to C, which is also solved recursively.

## Implementation

The `solve()`

method below implements the recursive algorithm. The following are the parameters:

`n`

: the number of disks to move`from`

: the source peg number`to`

: the destination peg number`temp`

: the temporary peg

For example, the following `main()`

method solves the puzzle of 4 disks, moving from peg 1 to peg 3, using peg 2 as temporary storage.