## **Note: this wiki is now retired and will no longer be updated!**

**The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.**

# SICP exercise 2.19

## Problem

Consider the change-counting program of section 1.2.2 of the text. It would be nice to be able to easily
change the currency used by the program, so that we could compute the number of ways to change a British
pound, for example. As the program is written, the knowledge of the currency is distributed partly into the
procedure `first-denomination` and partly into the procedure `count-change` (which knows that
there are five kinds of U.S. coins). It would be nicer to be able to supply a list of coins to be used for
making change.

We want to rewrite the procedure `cc` so that its second argument is a list of the values of the coins to use
rather than an integer specifying which coins to use. We could then have lists that defined each kind of
currency:

(define us-coins (list 50 25 10 5 1)) (define uk-coins (list 100 50 20 10 5 2 1 0.5))

We could then call cc as follows:

(cc 100 us-coins)

*Output:*

`
`

292

To do this will require changing the program `cc` somewhat. It will still have the same form, but it will
access its second argument differently, as follows:

(define (cc amount coin-values) (cond ((= amount 0) 1) ((or (< amount 0) (no-more? coin-values)) 0) (else (+ (cc amount (except-first-denomination coin-values)) (cc (- amount (first-denomination coin-values)) coin-values)))))

Define the procedures `first-denomination`, `except-first-denomination`, and `no-more?`
in terms of primitive operations on list structures. Does the order of the list `coin-values` affect the
answer produced by `cc`? Why or why not?

## Solution

Part one of the exercise asks us to define the procedures
`first-denomination`, `except-first-denomination` and `no-more?` in terms
of primitive operations on list structures. This part is easy:

(define (first-denomination coin-values) (car coin-values)) (define (except-first-denomination coin-values) (cdr coin-values)) (define (no-more? coin-values) (null? coin-values))

Test:

(cc 100 us-coins)

*Output:*

`
`

292

(cc 11 uk-coins)

*Output:*

`
`

62

Part two asks if the order of the list `coin-values` affects the
answer produced by `cc`.

The answer does *not* depend on the order of the list because `cc`
exhaustively traverses the list when calculating the answer. Recall
that the process generated by `cc` takes the shape of a tree. It
terminates the evaluation of a branch only when the list is empty or when
the amount of change remaining is less than or equal to zero.
Termination of the branch does not depend on the magnitude of the
remaining values in the list.

We can verify our answer by reversing the `us-coins` and `uk-coins`
lists and comparing the answers using the reversed lists to the
answers we got using the original lists:

(cc 100 (reverse us-coins))

*Output:*

`
`

292

(cc 11 (reverse uk-coins))

*Output:*

`
`

62

Note that we **could** require the `types-of-coin` list to be sorted
from lowest to highest denomination, and then change `cc` to take
advantage of this restriction by aborting evaluation branches when the amount of
change remaining is less than the first denomination. The modified
`cc` would evaluate fewer nodes.