An Awesome Recursive Solution

The best way to figure out a solution is to think logically and recursively. Break down the problem into a smaller version of itself.

If we can somehow figure out how to move N-1 disks from source shelf to intermediate shelf, using the destination as an intermediate location, then we can move the biggest disk from source to destination. Next, we can move the N-1 disks from intermediate shelf to the target, using source shelf as intermediate location. The diagram below will help in visualizing this.

The pseudo-code is therefore very simple.

xxxxxxxxxx

Recurisve routine: Hanoi

Input: source shelf, target shelf, intermediate shelf, N disks placed on source shelf

Target: N disks placed on target shelf

​

Base case:

1. If there are zero disks then stop.

Recursive case:

1. Move (N-1) disks from source to intermediate using destination as intermediate shelf

2. Shift the last disk from source to destination

3. Move (N-1) disks from intermediate to destination using source as intermediate shelf