Change, coins. Change is made with a recursive method. This sort of problem, as described in the Structure and Interpretation of Computer Programs, can be solved with recursion.
This implementation in the C# language is illustrative. For most of these puzzles, implementing the code yourself (with a little help) is a good way to learn.
Example. This program uses recursion to compute different ways of making change to match a specified amount. Change() will print out all the ways you can make change for a specified amount.
Detail If you specify 51 cents, it will tell you can make this out of 36 1-cent coins and three 5-cent coins.
Detail The 2 Lists store the currently recorded values, and the amounts or denominations of coins that are possible to be used.
Note The program emphasizes the recursive Change method. This implements the logic that actually computes the change.
Tip In many recursive methods, it is clearest to add the exit conditions at the start of the function.
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static void Main()
{
List<int> coins = new List<int>();
List<int> amounts = new List<int>() { 1, 5, 10, 25, 50 };
//
// Compute change for 51 cents.
//Change(coins, amounts, 0, 0, 51);
}
static void Change(List<int> coins, List<int> amounts, int highest, int sum, int goal)
{
//
// See if we are done.
//
if (sum == goal)
{
Display(coins, amounts);
return;
}
//
// See if we have too much.
//
if (sum > goal)
{
return;
}
//
// Loop through amounts.
//
foreach (int value in amounts)
{
//
// Only add higher or equal amounts.
//
if (value >= highest)
{
List<int> copy = new List<int>(coins);
copy.Add(value);
Change(copy, amounts, value, sum + value, goal);
}
}
}
static void Display(List<int> coins, List<int> amounts)
{
foreach (int amount in amounts)
{
int count = coins.Count(value => value == amount);
Console.WriteLine("{0}: {1}",
amount,
count);
}
Console.WriteLine();
}
}1: 51
5: 0
10: 0
25: 0
50: 0
1: 46
5: 1
10: 0
25: 0
50: 0
1: 41
5: 2
10: 0
25: 0
50: 0
1: 41
5: 0
10: 1
25: 0
50: 0
1: 36
5: 3
10: 0
25: 0
50: 0
Notes, Change method. Change() first tests for the ideal amount, and if this is reached, it prints it to the screen. It tests to make sure the change collected has not exceeded the target.
Notes, size. This algorithm only adds coins in increasing size. It starts with the 1-cent coin and continues with the 5-cent coin and then larger coins. The output is automatically sorted.
Output. Display() prints the frequencies of the coins that can be added together to reach the target value. In the example, all of the output will add up to 51 cents.
Detail It shows 51 cents being composed of 51 1-cent coins. This is obviously a correct answer.
Detail It shows 51 cents being made up of 46 1-cent coins and one 5-cent coin.
SICP. The Structure and Interpretation of Computer Programs book uses this example in its first chapter. It counts ways to compute change for 100 cents. See section 1.2.2 Tree Recursion.
Detail The answer of 292 is computed from interpreting the Lisp program. On the C# program shown here, you will also get 292 answers.
Also If you modify the program to include a counter, it is clearer that the result is 292.
Performance. This program is far from ideal for performance. A variety of approaches could be used to transform the process into a faster one.
Tip You could use arrays instead of List types, and could use a Stack structure instead of a recursive method.
Performance, continued. You could improve the loop with a faster algorithm that jumps to the correct starting index based on the current top value. This could be done with a lookup table.
A summary. We wrote an example program that makes change to match a specified amount. It uses a recursive method invocation and the List type to solve a puzzle.
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.