Make-change: Beginner Trouble

338 views Asked by At

I'm trying to create "make-change" that will return a ls of coins whose sum = the input, and it needs to contain the least number of coins possible. Ex: (make-change 99)

=> (quarter quarter quarter dime dime penny penny penny penny)

1

There are 1 answers

4
mqp On BEST ANSWER

Here's the lines along which make-change should operate:

  • If the remaining amount is exactly equal to 1, 5, 10, or 25 then return the appropriate coin.
  • Otherwise, cons the largest coin you can use onto the result of (make-change (- x value)) where value is the amount of the coin that you just used.

You can tell this procedure will terminate, since the amount will become smaller and smaller via step 2 until it is finally amenable to concluding with step 1.