SICP 2.19: Counting Change Revisited

From SICP section 2.2.1 Representing Sequences

Exercise 2.19 asks us to modify the change counting procedure from section 1.2.2 (which we looked at in depth in exercise 1.14). We need to modify the program so that it takes a list of coins to be used instead of having the denominations hard coded as they were originally. The following lists of coins are provided:

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

We're also provided with the following modified version of the cc procedure:

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

All that's left for us to do is define the procedures first-denomination, except-first-denomination, and no-more? in terms of primitive list operations. These procedures are very straightforward.

; return true if passed an empty list
(define (no-more? coin-values)
  (if (null? coin-values) true false))

; return all coin values except the first
(define (except-first-denomination coin-values)
  (cdr coin-values))

; return only the first coin value
(define (first-denomination coin-values)
  (car coin-values))

> (cc 100 us-coins)
292
> (cc 100 uk-coins)
104561

Finally, we're asked if the order of the list coin-values affects the answer produced by cc. We can find out quickly enough by experiment.

; reversed list of us coins
(define su-coins (list 1 5 10 25 50))

> (cc 100 us-coins)
292
> (cc 100 su-coins)
292

We can see that the order doesn't matter. This is because the procedure recursively evaluates every sub-list after subtracting the value of the first coin from the target amount. It doesn't matter if that value is the smallest, largest, or even if the values are shuffled.


Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.