Code: Tower of Hanoi using Recursion | DSA in C++ - Software Development PDF Download

Here's a C++ code to solve the Tower of Hanoi problem using recursion:

#include <iostream>

void towerOfHanoi(int n, char source, char auxiliary, char destination) {

    if (n == 1) {

        // Base case: If there is only one disk, move it from source to destination

        std::cout << "Move disk 1 from " << source << " to " << destination << std::endl;

        return;

    }

    // Move n-1 disks from source to auxiliary peg

    towerOfHanoi(n - 1, source, destination, auxiliary);

    // Move the nth disk from source to destination

    std::cout << "Move disk " << n << " from " << source << " to " << destination << std::endl;

    // Move the n-1 disks from auxiliary peg to destination peg

    towerOfHanoi(n - 1, auxiliary, source, destination);

}

int main() {

    int numDisks;

    std::cout << "Enter the number of disks: ";

    std::cin >> numDisks;

    std::cout << "Tower of Hanoi solution:" << std::endl;

    towerOfHanoi(numDisks, 'A', 'B', 'C');

    return 0;

}

Output:

Enter the number of disks: 3

Tower of Hanoi solution:

Move disk 1 from A to C

Move disk 2 from A to B

Move disk 1 from C to B

Move disk 3 from A to C

Move disk 1 from B to A

Move disk 2 from B to C

Move disk 1 from A to C

Explanation:

• The towerOfHanoi function is a recursive function that solves the Tower of Hanoi problem. It takes four parameters: 'n' (the number of disks), 'source' (the source peg), 'auxiliary' (the auxiliary peg), and 'destination' (the destination peg).
• The base case is defined when there is only one disk ('n == 1'). In this case, it simply moves the disk from the source peg to the destination peg and prints the move.
• For the recursive case ('n > 1'), the function follows the following steps:
• a. Move 'n-1' disks from the source peg to the auxiliary peg using the destination peg as the temporary peg. This is done by making a recursive call to 'towerOfHanoi' with the parameters: 'n-1', source peg, destination peg, and auxiliary peg.
• b. Move the nth disk from the source peg to the destination peg and print the move.
• c. Move the 'n-1' disks from the auxiliary peg to the destination peg using the source peg as the temporary peg. This is done by making another recursive call to towerOfHanoi with the parameters: 'n-1', auxiliary peg, source peg, and destination peg.
• In the 'main' function, the user is prompted to enter the number of disks.
• The 'towerOfHanoi' function is called with the initial values: number of disks, source peg ('A'), auxiliary peg ('B'), and destination peg ('C').
• The solution is printed by the function as it performs the necessary moves.

The Tower of Hanoi problem is a classic example of recursion, where a larger problem is broken down into smaller subproblems. The recursive solution follows the concept of divide and conquer, solving the smaller subproblems and combining the solutions to solve the original problem.