Java Recursion Example: Count Change

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.

ArrayList

Display: This loops over all coins amounts. It counts the coins added in each amount. It displays the results.

Println

Main: Here we create our amounts array with coin denominations. We specify a goal of 51 cents and call change().

Array

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.

The Dev Codes

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

TheDeveloperBlog.com

Java Recursion Example: Count Change

Related Links:

.Net

Java

Related Links