Recursion. Some problems are hard to solve. We must perform an exhaustive search of all possibilities. Making change, to a certain amount of money, is an example.
In making change, we add coins to a collection until we reach a goal amount. We must use combinations of different coins. Many possible solutions exist.
A recursive method. We introduce a recursive method, change(), to count change. An ArrayList called "coins" stores the coins we have added. And an array, amounts, stores possible coins.
Detail This method checks to see if we have reached the goal. Then it tries to add a coin, placing it in a copied ArrayList.
import java.util.ArrayList;
public class Program {
public static void change(ArrayList<Integer> coins, int[] amounts,
int highest, int sum, int goal) {
// See if we have reached the goal.
if (sum == goal) {
display(coins, amounts);
return;
}
// We cannot go over our goal.
if (sum > goal) {
return;
}
// Add higher amounts to a new ArrayList.
for (int value : amounts) {
if (value >= highest) {
ArrayList<Integer> copy = new ArrayList<>();
copy.addAll(coins);
copy.add(value);
// Recurse to check total and add further coins.
change(copy, amounts, value, sum + value, goal);
}
}
}
public static void display(ArrayList<Integer> coins, int[] amounts) {
// Count each amount within the added coins.// ... Then display the amount and count.
for (int amount : amounts) {
int count = 0;
for (int coin : coins) { // Count loop.
if (coin == amount) {
count++;
}
}
System.out.print(amount);
System.out.print(":");
System.out.println(count);
}
System.out.println();
}
public static void main(String[] args) {
ArrayList<Integer> coins = new ArrayList<>();
// This array contains the coin amounts.
int[] amounts = { 1, 5, 10, 25, 50 };
// Solve for 51 cents.
change(coins, amounts, 0, 0, 51);
}
}1:51
5:0
10:0
25:0
50:0
1:46
5:1
10:0
25:0
50:0
...
1:1
5:0
10:0
25:0
50:1
Its results. The groups of possible coins is displayed. We can make 51 cents with 51 one-cent pieces. Or we can use 46 one-cent pieces and 1 five-cent piece.
Finally The last result is 1 one-cent piece and 1 fifty-cent piece. It all correctly adds up.
Concepts. Often recursive methods first check for "out of range" cases and return early if one is detected. In our method, we check for the goal amount, and test it is not exceeded.
Detail It is important to copy a collection like an ArrayList. If the ArrayList is not copied, the algorithm will fail.
Detail This implementation is not ideal. It could be optimized by reducing the looping in display().
Detail Using arrays, not ArrayLists, is typically faster. These ideas could be part of an optimization exercise.
This exercise is part of the Structure and Interpretation of Computer Programs. It is implemented in Scheme, but the end result, combinations of coins, is the same.
Recursion solves many problems. But often, in real-world programs (not exercises) iteration is superior. It is easier to write, faster to run, and leads to less complexity.
Dot Net Perls is a collection of tested code examples. Pages are continually updated to stay current, with code correctness a top priority.
Sam Allen is passionate about computer languages. In the past, his work has been recommended by Apple and Microsoft and he has studied computers at a selective university in the United States.