Recitation #7 Notes, Wed, 9/17/97

A procedure whose values from 0 to 5 are the six existing denominations,
in pennies, of US coins:

(define (us-coins k)
  (cond ((= k 0) 100)
        ((= k 1) 50)
        ((= k 2) 25)
        ((= k 3) 10)
        ((= k 4) 5)
        ((= k 5) 1)
        (else (error "only 6 different denominations" k))))


(define (canadian-coins k)
  (if (zero? k)
      200                               ;Canadians have a 2 dollar coin
      (us-coins (- k 1))))

Note that if the US Mint changes coinage, we now have to update BOTH
us-coins AND canadian-coins.  This is not good software design.  We'll use
it anyway, for now.

The procedure CC, for "count-change", expects a procedure
coin-denominations to be defined.  We'll start with

(define coin-denominations us-coins)

Now (CC amount n) is supposed to return the number of possible ways of
making change for AMOUNT -- a nonnegative integer -- using only coins with
denominations (coin-denominations k) for k = 0, 1, .., n.  Since there are
6 US coin denominations, (CC amount 6) will therefore return the total
number of ways to make change for AMOUNT in US coins.

The idea is that the ways to make change for AMOUNT with n coins can be
split into two separate groups:
(i) the ways which use 1 or more coins of denomination n, and
(ii) the ways which use no coins of denomination n.

But (i) is exactly the ways to make change for AMOUNT minus the
denomination of the nth coin, freely using coins of the first n
denominations,

and (ii) is exactly the ways to make change for AMOUNT using only the
first n-1 denominations.

These facts yield a recursive procedure:

(define (cc amount n)
  (cond ((zero? amount) 1)       ;the only way to make change for 0 is using no coins
        ((or (< amount 0) (zero? n)) 0) ;no way to make change for amount > 0 with no coins
        (else (+ (cc (- amount (coin-denominations n)) n)
                 (cc amount (- n 1))))))

(Except for renaming, this is from SICP, p. 41.)

It is tree-recursive:

                                       (cc 425 3)
                                        /      \
                   (cc 325 3)                                  (cc 425 2)
                    /      \                                   /      \
              (cc 225 3)   (cc 325 2)                     (cc 375 1)   (cc 425 1)
              /        \   /        \                     /        \   /        \
      (cc 125 3)
      /        \
  (cc 25 3)
  /       \
(cc -75 3)
     |
     0