algorithmrecursionschemesicpcoin-change# SICP example: Counting change, cannot understand

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.

Solution

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.

- Divide to the subparts of the same nature

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.

- conquer

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.

- combine

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.

- Find permutation of array - Where am I going wrong?
- Second highest number ArrayList
- Sort (hex) colors to match rainbow
- Implementing a Harris corner detector
- algorithm for find lowest subsequence of items in 2 sets
- Problem in thinking recursively. How to take recursive leap of faith?
- Is there a name for this "fill in the blank" algorithm?
- Bitwise operation without using any predefined C functions
- `std::list<>::sort()` - why the sudden switch to top-down strategy?
- How to get the water level in each bar of a histogram after raining?
- How to combine date ranges in PHP
- How to space neighbouring wireless transmissions temporally?
- Generating a graph with certain degree distribution?
- Find the coin change (Greedy Algorithm) when coins are in decimals and returned amount in coins is larger then original return value
- Find a specific word algorithm in c++
- Minimum number of inversions to make one array identical to another
- flattening a list of contracts based on priority
- Why complexity of removing last element from List is O(1) and O(n) for the arrays?
- Largest rectangle of 1's in 2d binary matrix
- How to group a square grid diagonally
- Bellman Ford Algorithm not detecting negative weight cycles and won't work with alternate sources
- Find Maximum Integer in Array?
- Staircase problem - Varying base cases in different coditions
- BFS algorithm in python
- Quicksort algorithm from a textbook fails to properly sort an array
- Given multiple sets, how do I find the smallest subset of each set that is unique to all other subsets?
- Determining if there exists numbers n1, n2 in a, b and n3 in c such that n1 + n2 = n3 [ftt, polynomial multiplication]
- Problem with recursive calls when x only takes t time, but when 10x it needs 100t time and much slower
- An algorithm for inflating/deflating (offsetting, buffering) polygons
- Optimization trading items - min cost max flow