C# Change

Structure and Interpretation of Computer Programs

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.

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: 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
Squares: abstract

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.

IfSteps

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

Console screenshot

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

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.

ArrayStack

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

C# programming language

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.


C#: Method