Spoiler Alert!
*** SICP Homework - PART TWO ***
Thus, we can recursively reduce the problem of changing a given amount to the problem of changing smaller amounts using fewer kinds of coins. Consider this reduction rule carefully, and convince yourself that we can use it to describe an algorithm if we specify the following degenerate cases:
* If a is exactly 0, we should count that as 1 way to make change.
* If a is less than 0, we should count that as 0 ways to make change.
* If n is 0, we should count that as 0 ways to make change.
we can easily translate this description into a recursive procedure:
(defun count
-change
(amount
) (cc amount 5) )
(defun cc
(amount kinds
-of
-coins
) ((or (< amount
0) (= kinds
-of
-coins
0)) 0) (else (+ (cc amount
(- kinds-of-coins 1))
(cc (- amount
(first-denomination kinds-of-coins))
kinds-of-coins)))))
(defun first
-denomination
(kinds
-of
-coins
) (cond ((= kinds
-of
-coins
1) 1) ((= kinds-of-coins 2) 5)
((= kinds-of-coins 3) 10)
((= kinds-of-coins 4) 25)
((= kinds-of-coins 5) 50)) )
The first-denomination procedure takes as input the number of kinds of coins available and returns the denomination of the first kind. Here we are thinking of the coins as arranged in order from largest to smallest, but any order would do as well. We can now answer our original question about changing a dollar:
(count-change 100)
292
Count-change generates a tree-recursive process with redundancies similar to those in our first implementation of fib. (It will take quite a while for that 292 to be computed.) On the other hand, it is not obvious how to design a better algorithm for computing the result, and we leave this problem as a challenge. The observation that a tree-recursive process may be highly inefficient but often easy to specify and understand has led people to propose that one could get the best of both worlds by designing a ``smart compiler'' that could transform tree-recursive procedures into more efficient procedures that compute the same result.
*** SICP Homework - PART TWO ***