Tower of hanoi

1. Problem Explanation

The Tower of Hanoi is a classic recursive problem.
You are given:

• Three pegs: A (source), B (auxiliary), C (destination)
• n disks of different sizes placed on peg A
• Larger disk cannot be placed on smaller disk
• Move all disks from peg A → C, using peg B as helper

2. Rules

1. Only one disk can be moved at a time.
2. A disk can be placed only on an empty peg or on a larger disk.
3. Use peg B as auxiliary.

3. Recursive Idea

To move n disks from A → C:

1. Move n-1 disks from A → B (using C)
2. Move last disk (nth) from A → C
3. Move n-1 disks from B → C (using A)

Figure: Recursion Tree for Tower of Hanoi (n = 3)

4. Recurrence Relation

Base case:

Solution of recurrence:

5. Algorithm

TOH(n, source, auxiliary, destination):

    if n == 1:
        print("Move disk 1 from", source, "to", destination)
        return

    TOH(n-1, source, destination, auxiliary)

    print("Move disk", n, "from", source, "to", destination)

    TOH(n-1, auxiliary, source, destination)

6. Time Complexity

So the time complexity is:

Exponential — O(2ⁿ)

7. Space Complexity

Recursion depth is n:

8. Example (n = 3)

Sequence of moves:

1. A → C
2. A → B
3. C → B
4. A → C
5. B → A
6. B → C
7. A → C

Total moves: