Java - Recursion Example: Count Change

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.

Info The change() method checks to see if we have reached the goal. Then it tries to add a coin, placing it in a copied ArrayList.

ArrayList

Next The for-loop loops over all coins amounts. It counts the coins added in each amount. It displays the results.

Console

Start In main() we create our amounts array with coin denominations. We specify a goal of 51 cents and call change().

Array

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.

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

Summary. 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.