Use recursion to calculate change. Keep track of coins and display them when complete.

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.

Change: This method checks to see if we have reached the goal. Then it tries to add a coin, placing it in a copied ArrayList.

Java program that uses recursion, makes change
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);
}
}
Output
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.

Copy: It is important to copy a collection like an ArrayList. If the ArrayList is not copied, the algorithm will fail.

Performance: This implementation is not ideal. It could be optimized by reducing the looping in display().

Arrays: 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.