Tower of hanoi

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: