# Tower of Hanoi

\[Math, Recursion]

Tower of Hanoi is a mathematical puzzle where we have 3 rods and n disks. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
3. No disk may be placed on top of a smaller disk.

Write a program which prints a sequence of operations that move n disks from one rod to another.

**Example for 3 disks**:\
[![faq.disk3](https://contribute.geeksforgeeks.org/wp-content/uploads/tower-of-hanoi.png)](https://contribute.geeksforgeeks.org/wp-content/uploads/tower-of-hanoi.png)

Reference: EPI python, page 226

## Solution: Recursion

**Idea**:

* Use recursion. Think about if we know how to move the top n-1 disks, how can we move n disks.

**Time complexity**: $$O(2^n)$$ because in the recursion we have $$T(n) = 2 T(n-1) + 1$$

**Space Complexity**: $$O(1)$$

```python
def tower_of_hanoi(n):
    # Recursive function to solve tower of hanoi   
    def helper(n , from_rod, to_rod, aux_rod): 
        # this recursion covers base cases

        # move top n-1 disks to aux_rod
        helper(n-1, from_rod, aux_rod, to_rod) 
        # move the nth disk to to_rod
        print "Move disk",n,"from rod",from_rod,"to rod",to_rod 
        # move top n-1 disks to to_rod
        helper(n-1, aux_rod, to_rod, from_rod) 

    helper(n, 'A', 'B', 'C')  
    # A, C, B are the name of rods
```