(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