The classic Towers of Hanoi problem can be solved easily using recursion, but it is difficult to solve otherwise.
The Towers of Hanoi problem is a classic recursion example. It can be solved easily using recursion but is difficult to solve otherwise.
The problem involves moving a specified number of disks of distinct sizes from one tower to another while observing the following rules:
- There are ndisks labeled 1, 2, 3, . . . , n,and three towers labeled A, B, and C.
- No disk can be on top of a smaller disk at any time.
- All the disks are initially placed on tower A.
- Only one disk can be moved at a time, and it must be the top disk on the tower.
The objective is to move all the disks from A to B with the assistance of C. For example, if you have three disks, the steps to move all of the disks from A to B are shown in Figure 17.5.
In the case of three disks, you can find the solution manually. For a larger number of disks, however—even for four—the problem is quite complex. Fortunately, the problem has an inherently recursive nature, which leads to a straightforward recursive solution.
The base case for the problem is n = 1. If n == 1, you could simply move the disk from A to B. When n > 1, you could split the original problem into three subproblems and solve them sequentially.
- Move the first n – 1 disks from A to C recursively with the assistance of tower B, as shown in Step 1 in Figure 17.6.
- Move disk n from A to B, as shown in Step 2 in Figure 17.6.
- Move n – 1 disks from C to B recursively with the assistance of tower A, as shown in Step 3 in Figure 17.6.
The following function moves n disks from the fromTower to the toTower with the assistance of the auxTower:
void moveDisks(int n, char fromTower, char toTower, char auxTower)
The algorithm for the function can be described as follows:
if (n == 1) // Stopping condition
Move disk 1 from the fromTower to the toTower;
else
{
moveDisks(n – 1, fromTower, auxTower, toTower);
Move disk n from the fromTower to the toTower;
moveDisks(n – 1, auxTower, toTower, fromTower);
}
Listing 17.7 prompts the user to enter the number of disks and invokes the recursive function moveDisks to display the solution for moving the disks.
Listing 17.7 TowersOfHanoi.cpp
1 #include <iostream>
2 using namespace std;
3
4 // The function for finding the solution to move n disks
5 // from fromTower to toTower with auxTower
6 void moveDisks(int n, char fromTower,
7 char toTower, char auxTower)
8 {
9 if (n == 1) // Stopping condition
10 cout << “Move disk ” << n << ” from ” <<
11 fromTower << ” to ” << toTower << endl;
12 else
13 {
14 moveDisks(n – 1, fromTower, auxTower, toTower);
15 cout << “Move disk ” << n << ” from ” <<
16 fromTower << ” to ” << toTower << endl;
17 moveDisks(n – 1, auxTower, toTower, fromTower);
18 }
19 }
20
21 int main()
22 {
23 // Read number of disks, n
24 cout << “Enter number of disks: “;
25 int n;
26 cin >> n;
27
28 // Find the solution recursively
29 cout << “The moves are: ” << endl;
30 moveDisks(n, ‘A’, ‘B’, ‘C’);
31
32 return 0;
33 }
This problem is inherently recursive. Using recursion makes it possible to find a natural, simple solution. It would be difficult to solve the problem without using recursion.
Consider tracing the program for n = 3. The successive recursive calls are shown in Figure 17.7. As you can see, writing the program is easier than tracing the recursive calls. The system uses stacks to trace the calls behind the scenes. To some extent, recursion provides a level of abstraction that hides iterations and other details from the user.
Source: Liang Y. Daniel (2013), Introduction to programming with C++, Pearson; 3rd edition.