I am a beginner following SICP course on MIT OpenCourseWare using both the video lectures and the book available online. Yesterday I came across an example, which ask if we can write a procedure to compute the number of ways to change any given amount of money.
This problem has a simple solution as a recursive procedure:
(define (count-change amount)
(cc amount 5))
(define (cc amount kinds-of-coins)
(cond ((= amount 0) 1)
((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)))))
(define (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)))
If you want to check more of it, I took it from here.
they are calculating the number (N) of ways of change a quatity (A) using K kinds of coins by adding:
the number of ways (X) of changing A without coins of the first type.
The number of ways (Y) of changing (A - D), where D is the denomination of the fisrt coin, using ALL K types of coins.
The problem is, I just don't understand this. Following, they try to explain saying:
"To see why this is true, observe that the ways to make change can be divided into two groups: those that do not use any of the first kind of coin, and those that do. Therefore, the total number of ways to make change for some amount is equal to the number of ways to make change for the amount without using any of the first kind of coin, plus the number of ways to make change assuming that we do use the first kind of coin. (Is the last sentence the same as the addition N = X + Y ? ) But the latter number is equal to the number of ways to make change for the amount that remains after using a coin of the first kind. (After using this coin, they refer to ways of making change with or without the first kind of coin? ) "
I understand how they implemented the recursive algorithm, but I am unable to see how they got there. English is not my native language, so I might be missing something. If you could explain me, using other terms, the logic behind the solution I would really appreciate it. Thanks.
If we think too hard on recursion, we already fail. Personally, I use two metaphors in thinking recursions. One is from the small book "the little schemer": The Seventh Commandment - Recur on the subparts that are of the same nature. Another is the divide-conquer-combine paradigm for designing algorithms. Essentially, they are the same thing in how to think recursively.
The problem has two variables: The number (N) of money and the kinds (K) of coins, therefore any division needs to meet the following: 1. reducing all variables: both N and K, 2. the subparts are the same nature so each subpart can be solved by the recursion process itself or be can solved directly. 3. all subparts together == the original one part, no more and no less.
The division in the solution divides the original problems into two subparts: the first subpart is all combinations that using the first coin (we can restate it that all combinations using at least one coin of the first coin in the same meaning). The remaining subpart is that all combinations using none of the first coin. N is reduced in the first subpart, K is reduced in the second part. Both are the same nature which can be solved recursively and they together are the original problem.
In this step, I think about the base cases. What are the all base cases when the problem is reduced to the minimal that can be given answers directly. In this solution, there are three base cases. 1st is the N is reduced to 0. 2nd is the N is reduced to the negative. 3rd is the coins is reduced to 0 but N is still positive.
How results are combined when the subparts are solved. In this solution, they are simply +.
What's more, if we are recursive on a list, the division is usually car of the list and cdr of the list. Usually car of list can be solved directly if itself isn't a list. cdr part should be solved recursively. The base case is the end of list if met.
B.T.W, I would highly recommend the little schemer for learning recursion. It is much better than any others on this particular point as far as I have read.