(define us-coins '(50 25 10 5 1))
(define uk-coins '(100 50 20 10 5 2 1 0.5))
(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 (no-more? coin-values)
(null? coin-values))
(define (except-first-denomination coin-values)
(cdr coin-values))
(define (first-denomination coin-values)
(car coin-values))
; The order of coin values does not matter.
; There is a one to one mapping of paths down the call tree to leaves for calls
; with amount = 0 and ways of making change.
;
; The value returned by cc is the sum of the values returned by the leaf calls.
; Because the only other value a leaf call returns is 0, the sum of the leaves
; is the same as the number of leaves returning 1. Because there is exactly one
; path to each leave, the sum = number of paths to a leave returning 1. Thus
; cc returns the number of call paths that end with amount = 0. By the theorem
; this means cc returns the correct answer. Note: the argument does not depend
; on the order of coin denominations.
;
; The mapping is
; Let (v1 v2 v3 .. vk) be the coin denominations
; Let ni (1 <= i <= k) specify a way of making change for amount a where
; ni = # of coins with denomination vi
; ie: a = sum ni*vi
; Let j = largest index with ni > 0
;
; ni maps to the call path
; cc a (v1 v2 v3 ... vk)
; go to the second child (the one that decrements amount by v1) n1 times
; go to the first child (the one that removes a denomination) 1 time
; ...
; go to the second child (the one that decrements amount by vi) ni times
; go to the first child (the one that removes a denomination) 1 time
; ...
; go to the second child (the one that decrements amount by vj) nj times
; amount = 0 -> return 1