# 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:

1 | [1] | | |

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:

- Move disks 1 to \(X-1\) from tower \(A\) to \(B\)
- Move disk \(X\) from tower \(A\) to \(C\)
- 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:

- Move disks 1 to \(X-2\) from tower \(A\) to \(C\)
- Move disk \(X-1\) from tower \(A\) to \(B\)
- 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:

1 | void moveDisks(int nDisks, int from, int to); |

It can recursively call the function itself:

1 | void moveDisks(int nDisks, int from, int to) { |

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 |

## Test result

1 | 3 |