Solving Problems with Recursion

To conclude our discussion of recursion, we take a look at several complex problems and how to approach them from a recursive standpoint. Our strategy will be to:

Identify the cases we can solve directly. These are base cases.
Determine how to express a general case in terms of smaller subproblems. This is the recursive case.

For the latter, the first step is to identify appropriate subproblems, and the second is to figure out how to express the solution for the whole problem in terms of the solutions to the subproblems. This leads to a recurrence relation, which we can then implement in code.

Pancake Sort

Suppose you want to sort a stack of irregular pancakes such that they are in order, with the smallest at the top and the largest at the bottom. So as not to contaminate the pancakes, you would like to do so just by repeatedly flipping a subset of the pancakes with a spatula, which reverses the set of pancakes above the spatula, as shown in Figure 93. The goal is to come up with a generalized algorithm for sorting the pancakes just by flipping substacks from any point in the stack to the top.

_images/sup_pancake_problem.light.svg — Figure 93 The pancake problem is to sort a stack of pancakes, where the only allowed move is to flip a subset of the stack from a point in the middle to the top.

We start by identifying cases we can solve directly. An empty stack or one with just a single pancake are trivially sorted, so these are the base cases.

We then need to identify a subproblem. For a stack of $n$ pancakes, a natural subproblem is to sort a stack of $n-1$ pancakes. So we now have to figure out how to reduce the problem of sorting $n$ pancakes to that of sorting $n-1$ pancakes – we just need the largest pancake on the bottom, and then the substack above that has $n-1$ pancakes that need sorting.

The final step is to come up with a way of getting the largest pancake to the bottom. We know that if that pancake is at the top, we can flip the whole stack to get it to the bottom. So now the problem is how to get the largest pancake to the top. Placing the spatula under that pancake and flipping the stack above does the trick.

Thus, we have identified our recurrence:

Nothing need be done for a stack of zero or one.
For $n$ pancakes where $n > 1$, we place the spatula under the largest pancake and flip, moving it to the top. We then flip the whole stack, moving the largest pancake to the bottom. We then repeat the process on the $n-1$ pancakes above the largest.

Figure 94 illustrates this recurrence.

_images/sup_pancake_sort.light.svg — Figure 94 The pancake-sort algorithm flips the largest pancake to the top, then the whole stack, then recurses on a smaller stack.

We can implement this algorithm in code to sort an array of integers, considering the top of the stack to be at the beginning of the array and the bottom at the end. We make use of the reverse() function we wrote previously to flip a subset of the stack.

void pancake_sort(int *stack, int size) {
  if (size > 1) {
    // find position of largest element
    int *largest = std::max_element(stack, stack + size);
    // flip the stack from the top to the largest element
    reverse(stack, largest);
    // flip the whole stack
    reverse(stack, stack + size - 1);
    // recurse on a smaller stack
    pancake_sort(stack, size - 1);
  }
}

Here, we use std::max_element() from the <algorithm> library to find the largest item in the stack.

Tower of Hanoi

The Tower of Hanoi puzzle consists of three rods with $n$ disks of varying size arranged in sorted order on the first rod, as shown in Figure 95. The objective is to move the entire stack of disks to another rod, while obeying the following constraints:

Only one disk can be moved at a time.
Only the top disk at a rod can be moved.
A larger disk may never be placed on top of a smaller one.

_images/sup_tower_of_hanoi_problem.svg — Figure 95 The Tower of Hanoi problem moves a stack of disks from an initial rod to a target rod.

To come up with an algorithm to solve this puzzle, we first identify the base cases that can be solved directly. For $n = 1$, the lone disk can be moved directly without violating the constraints, constituting our base case.

For $n > 1$, the subproblem is moving $n-1$ disks between rods. Then our task is to determine how to express the solution for moving $n$ disks in terms of the solution to moving $n-1$ disks. We observe that we can completely ignore the largest disk when moving the $n-1$ smaller disks; since any of the latter can be placed on the largest disk, the rod with the largest disk acts just like an empty rod. Thus, we can move the $n-1$ smaller disks as a stack of their own, from the start rod to the middle rod. We can then move the largest disk directly to the empty target rod. Then all that is left is to move the stack of $n-1$ smaller disks to the target rod.

Figure 96 illustrates this algorithm. We take the recursive leap of faith, assuming that we can move the smaller $n-1$ stack as a whole using recursion, without worrying about the details of how it is done. As long as the subproblem is closer to the base case than the original problem, we get to make the assumption that the subproblem will be solved correctly.

_images/sup_tower_of_hanoi_solution.svg — Figure 96 An algorithm for the Tower of Hanoi is to use recursion to move a smaller stack and move the largest disk on its own.

The following code implements the algorithm, printing out the moves required to move $n$ disks from a start to end rod:

// MODIFIES: cout
// EFFECTS:  Prints a move of disk n from start to end.
void move(int n, int start, int end) {
  std::cout << "Move disk " << n << " from rod " << start
            << " to rod " << end << std::endl;
}

// REQUIRES: n >= 1
// MODIFIES: cout
// EFFECTS:  Prints the sequence of moves required to move n disks
//           from start to end, using temp as the temporary rod.
void hanoi(int n, int start, int temp, int end) {
  if (n == 1) {
    move(n, start, end);
  } else {
    hanoi(n - 1, start, end, temp);
    move(n, start, end);
    hanoi(n - 1, temp, start, end);
  }
}

The result of hanoi(5, 1, 2, 3) is as follows:

Move disk 1 from rod 1 to rod 3
Move disk 2 from rod 1 to rod 2
Move disk 1 from rod 3 to rod 2
Move disk 3 from rod 1 to rod 3
Move disk 1 from rod 2 to rod 1
Move disk 2 from rod 2 to rod 3
Move disk 1 from rod 1 to rod 3
Move disk 4 from rod 1 to rod 2
Move disk 1 from rod 3 to rod 2
Move disk 2 from rod 3 to rod 1
Move disk 1 from rod 2 to rod 1
Move disk 3 from rod 3 to rod 2
Move disk 1 from rod 1 to rod 3
Move disk 2 from rod 1 to rod 2
Move disk 1 from rod 3 to rod 2
Move disk 5 from rod 1 to rod 3
Move disk 1 from rod 2 to rod 1
Move disk 2 from rod 2 to rod 3
Move disk 1 from rod 1 to rod 3
Move disk 3 from rod 2 to rod 1
Move disk 1 from rod 3 to rod 2
Move disk 2 from rod 3 to rod 1
Move disk 1 from rod 2 to rod 1
Move disk 4 from rod 2 to rod 3
Move disk 1 from rod 1 to rod 3
Move disk 2 from rod 1 to rod 2
Move disk 1 from rod 3 to rod 2
Move disk 3 from rod 1 to rod 3
Move disk 1 from rod 2 to rod 1
Move disk 2 from rod 2 to rod 3
Move disk 1 from rod 1 to rod 3

Counting Change

As a final example, let us consider the number of ways we can change a dollar into coins, using any quantity of half dollars (50¢), quarters (25¢), dimes (10¢), nickels (5¢), and pennies (1¢). The following are three possible ways:

$1 = 1 half dollar, 1 quarter, 2 dimes, 1 nickel
$1 = 2 quarters, 2 dimes, 30 pennies
$1 = 100 pennies

There are too many ways to enumerate them all manually. Instead, let’s take a look at a smaller example of the same problem: the number of ways to make change for 11¢ using dimes, nickels, and pennies. There are exactly four:

11¢ = 1 dime, 1 penny
11¢ = 2 nickels, 1 penny
11¢ = 1 nickel, 6 pennies
11¢ = 11 pennies

We can categorize these solutions according to which coins they use, as shown in Figure 97.

_images/sup_counting_change.light.svg — Figure 97 The ways to count change can be subdivided into those that use a particular coin and those that don’t.

If we decide to use a particular coin, we are left with the subproblem of making a smaller amount of change using the same set of coins. For example, if we choose to use a dime, we need only make 1¢ using dimes, nickels, and pennies. On the other hand, if we choose not to use a particular coin, we must make the full amount of change with a smaller set of coins. In our example, if we decide not to use a dime, we must make the full 11¢ with only nickels and pennies. If we then use a nickel, we are left with making 6¢ with only nickels and pennies.

Figure 98 illustrates a decision tree for how to make change. At any point in time, we have a target amount and a set of available coins. We then decide whether to use the largest of our available coins. Either decision leads to a subproblem:

Making a smaller amount of change with the same set of available coins.
Making the same amount of change with a smaller set of available coins.

_images/sup_change_decision_tree.svg — Figure 98 The decision tree for which coin to use consists of a subtree that uses a particular coin and another that doesn’t.

Thus, we have a recurrence that expresses the solution for a full problem in terms of two subproblems.

We also need to identify base cases that we can solve directly:

If the change amount is zero, there is only one way to do that: use no coins.
If the change amount is negative, there is no way to do that, since we do not have negative coins.
If the change amount is positive but we have no coins available, we cannot make that change.

The following implements the resulting algorithm in code:

// EFFECTS: Returns the number of ways to make amount in change
//          using only the coin denominations in kinds.
int count_change(int amount, const int kinds[], int num_kinds) {
  if (amount == 0) {
    // one way to make nothing: use no coins
    return 1;
  } else if (amount < 0 || num_kinds < 1) {
    // cannot make negative amount, or anything with no coins
    return 0;
  } else {
    return
      // use the largest coin, reducing the amount of change to make
      count_change(amount - kinds[num_kinds - 1], kinds, num_kinds) +
      // don't use the largest coin, reducing the available coins
      count_change(amount, kinds, num_kinds - 1);
  }
}

This tree-recursive implementation is very inefficient, repeating the same computations many times. Techniques such as memoization and dynamic programming can drastically improve the efficiency, but they are beyond the scope of this course. (With such a technique in place, the result is 292 for the number of ways to make change for a dollar.)