# Tower of Hanoi

### Rules

1. Only one disc can be moved at a time
2. Each move consist of taking the top disc of one of the stacks and placing it on top of another stack / rod.
3. No larger disk may be placed on a smaller disc.

### Recursive solution

def hanoi(n, 1, 3, 2) // Move n disks from rod 1 - 3 using rod 2
if n > 0
hanoi(n - 1, 2, 3)
move disk n from rod 1 -> rod 3
hanoi(n - 1, 2, 3, 1)


### Lower bounds

Let the lower bound be some $$S(n)$$.

Consider two scenarios:

• What happened before disk n (relative position from top of a stack) is moved to the last rod 3

We have to move n - 1 discs on top of the nth disk first.

T(n - 1)

• What happened to move n disk on to rod 3

We have to move n - 1 discs to the rod 3.

T(n - 1)

Therefore we prove the minimum runtime,

T(0) = 0 T(n) = 2T(n - 1) + 1