Making change given the amount Scheme procedure

Question

The following code is to find out how many different ways can we make change given half-dollars, quarters, dimes, nickels, and pennies? Can someone explain how this procedure executes? How the cc function recurses? I tried tracing this procedure but I am not sure how the cc function can recurse when it subtracts the amount from the same denomination each time the function is called wouldn't the amount eventually reach 0? Also, I don't understand why are there 2 different recursive calls to cc? Any help would be appreciated.

      (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)))
     (count-change 10)

Try the stepper in DrRacket. (Choose the beginner language. Enter your example. Then click the foot). — soegaard

molbdnilo molbdnilo · Accepted Answer · 2020-12-30T10:04:40

The whole point is that the amount will eventually be zero; this is when the recursion ends.
(You might want to review your introduction to recursion.)

It executes like this:

If there is no change amount, there is exactly one way to give change,
If you don't have any coins, there is no way to give change,
Otherwise, you have two choices:
- Don't use the largest available coin, but give change on the whole amount using the smaller coins (the first recursion), or
- Use one of the largest coins, and give change on the remaining sum using all coins (the second recursion),
- And the result is the sum of these two options.

Making change given the amount Scheme procedure

1 Answers