# Tower of Hanoi with recursion

## Problem statement

Assume there are 3 towers and $$D$$ disks. And all disks are place at the first tower in a descending order in terms of disk number. It can be illustrated as follows:

The objective is to find out the order of movement to move the entire disks to another tower with constrains:

• One only disk can be moved at a time
• Disk $$X$$ cannot be placed under disk $$Y$$, where $$X$$ is greater than $$Y$$

## Approach

To move disk $$X$$ from tower $$A$$ to $$C$$, three steps as follows:

1. Move disks 1 to $$X-1$$ from tower $$A$$ to $$B$$
2. Move disk $$X$$ from tower $$A$$ to $$C$$
3. Move disks 1 to $$X-1$$ from tower $$B$$ to $$C$$

Steps (1) and (3) are not a single atomic operation and they can be performed recursively:

1. Move disks 1 to $$X-2$$ from tower $$A$$ to $$C$$
2. Move disk $$X-1$$ from tower $$A$$ to $$B$$
3. Move disks 1 to $$X-2$$ from tower $$C$$ to $$B$$

If there is only one disk to move, step (1) and step (3) can be skipped.

## Implementation

We can define a function moveDisks() whose inputs are the number of disks to be moved, tower number that the disks are currently located and tower number that the disks to be moved to:

It can recursively call the function itself:

Here int intermediate = 6 - from - to; is a tricky part. This variable represents the number of intermediate tower to move nDisks - 1 disks. If each tower is numbered with 1, 2, and 3 then relationships between from, to and intermediate can be determined as follows and the forementioned equation reflects these relationships:

From To Intermediate
1 2 3
1 3 2
2 1 3
2 3 2
3 1 2
3 2 3