How would you solve the Tower of Hanoi problem using recursion?

The Tower of Hanoi problem is a mathematical puzzle. It consists of three poles and a number of disks of different sizes, which can slide onto any pole. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape. 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 or on an empty rod.

3. No disk may be placed on top of a smaller disk.

We can solve the problem using a recursive approach. The key to the solution is to break the problem down into smaller subproblems.

We can write the recursive function to solve the problem as follows:

1. Move the top ‘n−1‘ disks from pole ‘A‘ (source pole) to pole ‘B‘ (auxiliary pole), using pole ‘C‘ (destination pole).

2. Move the remaining disk from pole ‘A‘ to pole ‘C‘.

3. Move the ‘n−1‘ disks from pole ‘B‘ to pole ‘C‘, using pole ‘A‘.

Let’s denote this function as ‘Hanoi(n, A, B, C)‘. The pseudocode for the function is as follows:

function Hanoi(n, source, auxiliary, target) {
    if (n > 0) {
        // Move n-1 disks from source to auxiliary, using target as temporary pole
        Hanoi(n-1, source, target, auxiliary);
        
        // Move the nth disk from source to target
        print "Move disk " + n + " from pole " + source + " to pole " + target;
        
        // Move the n-1 disks that we left on auxiliary to target
        Hanoi(n-1, auxiliary, source, target);
    }
}

Then, to solve the problem with ‘n‘ disks, you would call the function as ‘Hanoi(n, ’A’, ’B’, ’C’)‘.

The time complexity of the algorithm is given by the recurrence relation ‘T(n) = 2T(n-1) + O(1)‘. First, we ignore the minor operations ‘O(1)‘. The solution to this recurrence relation results in T(n) = 2ⁿ − 1 operations. Therefore, the time complexity of the Tower of Hanoi problem is O(2ⁿ).

This is because for each disk ‘n‘, we execute a recursive function twice to solve the subproblem of size ‘n-1‘. Hence, we have ‘2T(n-1)‘. The ‘+ O(1)‘ takes care of the moving operation.

The space complexity of the algorithm is ‘O(n)‘. This stems from the maximum depth of recursion we hit when using an explicit stack to keep track of function calls (recursion), which in the worst case is ‘n‘ (where ‘n‘ is the number of disks). Each function call requires a constant amount of space for housekeeping tasks and hence we get linear space complexity.

Let’s solve the problem for 3 disks:

Step 1: Call `Hanoi(3, 'A', 'B', 'C')`

- Call `Hanoi(2, 'A', 'C', 'B')`

    - Call `Hanoi(1, 'A', 'B', 'C')`
        - Call `Hanoi(0, 'A', 'C', 'B')` - Base case, do nothing
        - Move disk 1 from pole A to pole C
        - Call `Hanoi(0, 'B', 'A', 'C')` - Base case, do nothing
    - Move disk 2 from pole A to pole B
    - Call `Hanoi(1, 'C', 'A', 'B')`
        - Call `Hanoi(0, 'C', 'B', 'A')` - Base case, do nothing
        - Move disk 1 from pole C to pole B
        - Call `Hanoi(0, 'A', 'C', 'B')` - Base case, do nothing

- Move disk 3 from pole A to pole C

- Call `Hanoi(2, 'B', 'A', 'C')`
    - Call `Hanoi(1, 'B', 'C', 'A')`
        - Call `Hanoi(0, 'B', 'A', 'C')` - Base case, do nothing
        - Move disk 1 from pole B to pole A
        - Call `Hanoi(0, 'C', 'B', 'A')` - Base case, do nothing
    - Move disk 2 from pole B to pole C
    - Call `Hanoi(1, 'A', 'B', 'C')`
        - Call `Hanoi(0, 'A', 'C', 'B')` - Base case, do nothing
        - Move disk 1 from pole A to pole C
        - Call `Hanoi(0, 'B', 'A', 'C')` - Base case, do nothing

This results in the sequence of moves:

- Move disk 1 from pole A to pole C

- Move disk 2 from pole A to pole B

- Move disk 1 from pole C to pole B

- Move disk 3 from pole A to pole C

- Move disk 1 from pole B to pole A

- Move disk 2 from pole B to pole C

- Move disk 1 from pole A to pole C

So, this is the list of moves to solve the Tower of Hanoi problem for 3 disks.