The recursive cash changing algorithm

This is another one from Structure and Interpretation of Computer Programs which is a great book, but not a particularly easy read (not least because Scheme, the language in which the programs in the book is written is just different from C/Java etc). This example annoyed me for some time so I am writing down an explanation in case someone else wants to look it up…

Anyway this one is about the number of ways of to change cash. The algorithm is based on the fact that you can break down the number of ways to sort change of the sum n with t types of coin as follows:

• All ways to sort n with t-1 coins; plus
• All ways to sort n-d with t coins, where d is the denomination of the coin excluded in the above case.

(Think about it for five pence with two pence and one penny coins. One way to sort with pennies and two ways to change three pence with a two pences and pennies.)

To solve this recursively we have to define the degenerative cases – ie the points at which the recursion stops. These are:

• If the sum to be cashed to change is 0 then there is 1 way to do it;
• If the sum to be cashed to change is less than 0 then there are 0 ways to change it;
• If there are 0 coins then there are 0 ways to offer the change.

So how does it work … hopefully the graphic below shows how (changing 10 pence with fives, twos and ones):

The idea is that f(n, {c}) returns the number of ways n can be changed with the set of coins {c}. In this tree the number of leaf nodes (10) is the answer. I have cheated here – the turquoise leaves are not degenerate cases – each has to be worked down to a case where the one would apply if the algorithm is to be universal, though we can simply add an extra rule when the set of coins being used consists of only 1p coins – that is 1 way of sorting. (But if the universal rule was applied then the number of computing steps increases greatly – as each of those 1p cases has to be worked down to a degenerate case).

Update (27 March 2011): There were actually a couple of mistakes in how the terminating cases were shown in the graphic, fixed now I hope.

Related Articles

• Structure and Interpretation of Computer Programs (mitpress.mit.edu)
• Generating random mazes with the Growing Tree algorithm (w/ Javascript demo) (weblog.jamisbuck.org)
• QuoteComic #3: RECURSION (fortyfourfennecs.com)