C#:.NET:Method

.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 Row Sort Split Static StringBuilder Substring Switch Tuple

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.

Recursion

Example. This program uses 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.

Example: If you specify 51 cents, it will tell you can make this out of 36 1-cent coins and three 5-cent coins.

C# program that counts change

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: partial

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

In this example, 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.

ListInt

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.

This makes it easier to add more recursive invocations if required in the future. The Change method first tests for the ideal amount, and if this is reached, it prints it to the screen.

Also: The Change method tests to make sure the change collected has not exceeded the target.

If

This algorithm 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. For 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.

Console.WriteLine

The first output: It shows 51 cents being composed of 51 1-cent coins. This is obviously a correct answer.The second output: 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. Please look at section 1.2.2 Tree Recursion, and "Example: Counting Change."

SICP text: mit.edu

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.

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

Tip: You could use arrays instead of List types, and could use a Stack structure instead of a recursive method.

ArraysStack

Also, 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.

Foreach

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 duplicate the algorithm in the classic book Structure and Interpretation of Computer Programs.

Review: It is an illustrative example and also could have practical use in certain game-oriented programs.

Finally: We linked to the classic text Structure and Interpretation of Computer Programs at MIT.