Recursive Optimization
Table of contents
Choose-explore-unchoose
Consider the recursive method rollDice that prints out all of the possible outcomes of rolling a given number of dice.
public static void rollDice(int dice) {
rollDice(dice, "");
}
private static void rollDice(int dice, String chosen) {
if (dice == 0) {
System.out.println(chosen);
} else {
for (int value = 1; value <= 6; value += 1) {
rollDice(dice - 1, chosen + value);
}
}
}
Beyond solving problems with strings, many real-world recursive enumeration problems will use a data structure to represent solutions. However, working with data structures is more complicated than working with numbers and strings. What would happen if represented each solution in a list rather than string?
public static void rollDice(int dice) {
rollDice(dice, new ArrayList<Integer>());
}
private static void rollDice(int dice, List<Integer> chosen) {
if (dice == 0) {
System.out.println(chosen);
} else {
for (int value = 1; value <= 6; value += 1) {
// Add the dice roll value to the chosen outcomes
chosen.add(value);
rollDice(dice - 1, chosen);
}
}
}
This algorithm contains a bug that’s due to reference semantics work in Java!
Describe the bug in your own words.
There is only a single list of chosen outcomes shared between every recursive call! Consider what happens after rolling the first dice and add 1 to the chosen list of outcomes. The recursion here makes sense: we want to pass the updated list of chosen outcomes to the next recursive call. But when we eventually return from the rollDice call, the chosen list will have completely changed!
In order to undo the unintended changes to the chosen list, remove the choice after the recursive call has finished exploring the subproblem.
- Choose-explore-unchoose pattern
- For each option
- Choose the option.
- Explore the option.
- Unchoose the option.
public static void rollDice(int dice) {
rollDice(dice, new ArrayList<Integer>());
}
private static void rollDice(int dice, List<Integer> chosen) {
if (dice == 0) {
System.out.println(chosen);
} else {
for (int value = 1; value <= 6; value += 1) {
// Choose the option
chosen.add(value);
// Explore the option
rollDice(dice - 1, chosen);
// Unchoose the option
chosen.remove(chosen.size() - 1);
}
}
}
Enumeration problems
Let’s reflect on the recursive enumeration problems that we’ve solved thus far. Regardless of whether we represented each solution as a new string or as a list or as a stack, all of the problems involved recursively enumerating ordered lists with repetition.
- Ordered list with repetition
- A particular arrangement of elements where the order matters and each element may be used 0 or more times.
For example, in fourAB, we recursively enumerated all length-4 ordered lists of {A, B} with repetition. In both the string and list versions of rollDice, we recursively enumerated all dice-length ordered lists of {1, 2, 3, 4, 5, 6} with repetition.
Whereas choose-explore-unchoose was a strategy for adapting recursive enumeration (to lists rather than strings, for example), it’s not solving a fundamentally different type of problem. It turns out that there are many different types of problems that can be solved with the idea of recursive enumeration. We’ll also learn how to solve a second type of problem: recursively enumerating unordered sets without repetition.
- Unordered set without repetition
- A set of some (or all) elements where the order doesn’t matter and each element may be used either 0 or 1 times. Since elements cannot be repeated, each recursive subproblem must keep track of which remaining elements can still be used.
Optimization problems
Recursive enumeration allows us to print all solutions. But some problems don’t require enumerating all solutions.
- Optimization
- A type of problem that requires finding the optimal (best) solution from among a space of many potential candidate solutions.
- Combinatorial optimization
- A specific type of optimization problem whose potential candidate solutions can be generated recursively.
The main difference between enumeration and optimization is in how we combine the result of each subproblem to compute the complete result (the final step in the outline for defining recursive algorithms). In recursive enumeration algorithms, we typically don’t have to do anything for this step since the base case just prints out each solution, so recursive enumeration algorithms typically have a void return type. In contrast, recursive optimization algorithms need to return a single solution, so some additional work is needed to combine the result of each subproblem.
Backtracking
Recursive enumeration and recursive optimization are both solved by applying recursive backtracking.
- Recursive backtracking
- A recursive algorithm idea that solves problems by recursively generating solutions.
When solving any recursive backtracking problem, programmers ask three questions.
- What type of problem are we solving?
- Recursive enumeration.
- Recursive optimization.
- What is the form of a valid solution?
- Ordered lists with repetition.
- Unordered sets without repetition.
- What is the data type of a valid solution?
- Primitive types (such as numbers) or strings.
- Reference types (such as collections), which require choose-explore-unchoose.