C# Change: Coins

You want to make change out of coins to a specified amount using a recursive method in the C# programming language. 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 when compared to alternative implementations.

This C# tutorial shows how to develop a recursive method to make change.

Recursion

This example program demonstrates how you can use recursion in the C# language to compute different ways of making change to match a specified amount. The recursive method Change will print out all the ways you can make change for a specified amount. For example, if you specify 51 cents, it will tell you can make this out of 36 1-cent coins and three 5-cent coins.

Program that counts change [C#]

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();
    }
}

Output
    (This is partial output only.)

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

Main entry point. This program includes the Main entry point and this is where control flow begins and the program starts executing. The List type is used with the parameterized type integer. The two List instances declared store the currently recorded values (which starts empty), and the amounts or denominations of coins that are possible to be used. The second List could be a static field instead.

Understanding Change recursive method. The program text emphasizes the recursive Change method, and this implements the logic that actually computes the change. In many recursive methods, it is clearest to add the exit conditions at the very start of the function. This makes it easier to add more recursive invocations if required later on. The Change method first tests for the ideal amount, and if this is reached, it prints it to the screen. It also tests to make sure the change collected hasn't exceeded the target.

Algorithm description and ordering. An important part of this algorithm is that it only adds coins in increasing size. In other words, it starts with the 1-cent coin and continues with the 5-cent coin and then larger coins. This results in the output being automatically sorted.

Output. The Display method finally 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. The first output shows 51 cents being composed of 51 1-cent coins. The second output shows 51 cents being made up of 46 1-cent coins and one 5-cent coin.

SICP

The Structure and Interpretation of Computer Programs uses almost this exact same example in its first chapter, and you can see the implementation in the Scheme dialect in Lisp in the book online. In the book, the number of ways to compute change for 100 cents is determined. Please look at the section 1.2.2 Tree Recursion and look for Example: Counting Change.

Answer of 292. In the book, the answer of 292 is computed from interpreting the Lisp program. On the C# program shown here, you will get 292 answers printed to the screen if you give it the argument of 100 for the required amount. 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 work and would not be acceptable for an important application. A variety of approaches could be used to transform the process into a faster one. You could use arrays instead of List types, and could use a Stack structure instead of a recursive method. You could improve the foreach loop with a faster search algorithm that jumps to the correct starting index based on the current top value. This could be done with a lookup table.

Summary

We looked at an example program written in the C# programming language that makes change to match a specified amount. It uses a recursive method invocation and the List type to duplicate the algorithm described in the classic book Structure and Interpretation of Computer Programs. It is an illustrative example and also could have practical use in certain game-oriented programs. Finally, we linked to the Structure and Interpretation of Computer Programs at MIT.