Iterative "counting change" implementation in mit-scheme

Question

Here is my iterative implementation of the Counting change example in SICP. Please note that I'm a beginner, which means I only know the basic syntax for the time being.

Requirement:

How many different ways can we make change of $ 1.00, given half-dollars, quarters, dimes, nickels, and pennies? More generally, can we write a procedure to compute the number of ways to change any given amount of money?

Code:

(define (count-change-iterative amount)
  ;; penny is not in the signiture, bacause it equals (- amount
  ;;                                                     (* half-dollar 50)
  ;;                                                     (* quarter 25)
  ;;                                                     (* dime 10)
  ;;                                                     (* nickeli 5))
  (define (count-iter half-dollar quarter dime nickeli)
    (cond ((> (* half-dollar 50) amount)
           0)
          ((> (+ (* half-dollar 50)
                 (* quarter 25)) amount)
           (count-iter (+ half-dollar 1) 0 0 0))
          ((> (+ (* half-dollar 50)
                 (* quarter 25)
                 (* dime 10)) amount)
           (count-iter half-dollar (+ quarter 1) 0 0))
          ((> (+ (* half-dollar 50)
                 (* quarter 25)
                 (* dime 10)
                 (* nickeli 5)) amount)
           (count-iter half-dollar quarter (+ dime 1) 0))
          (else (+ 1
                   (count-iter half-dollar quarter dime (+ nickeli 1))))))
  (count-iter 0 0 0 0))

If you run (count-change-iterative 100), it would tell you 292.

I think this is the best scheme code I've written by now. How can I improve it?

Answer 1

In SICP the authors note:

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.

And while your solution is more efficient than the solution they provide it still has a lot of redundancies. If you're will to sacrifice some readability you could use a bottom-up algorithm to eliminate these redundancies.

For example:

(define (add-if predicate x addition)
  (if predicate (+ x addition) x))

(define (inc-if predicate x)
  (add-if predicate x 1))

(define (zero-if predicate x)
  (if predicate 0 x))

(define (count-change amount)
  (define (cc-iter value ways-to-change new-ways nickel-ways dime-ways quarter-ways nickels dimes quarters)
    (define (current-coins num-nickels num-dimes num-quarters)
      (and (= nickels num-nickels)
           (= dimes num-dimes)
           (= quarters num-quarters)))
    (if (> value amount)
        ways-to-change
        (cc-iter (+ value 5)
                 (+ ways-to-change new-ways)
                 (+ new-ways (if (= nickels quarters) dime-ways nickel-ways))
                 (add-if (current-coins 0 1 1) nickel-ways quarter-ways)
                 (add-if (current-coins 0 1 0) dime-ways quarter-ways)
                 (inc-if (current-coins 0 1 0) quarter-ways)
                 (zero-if (or (= nickels 1) (= dimes 2)) 1)
                 (zero-if (= dimes 2) (inc-if (= nickels 1) dimes))
                 (zero-if (current-coins 0 2 1) (inc-if (= dimes 2) quarters)))))
  (cc-iter 0 0 1 1 0 1 0 0 0))

Answer 2

If you add a running sum to the formal parameters of count-iter, you'll have a truly iterative piece of code. As-is, every time through count-iter is called, you leave a "1+ ??" waiting on the stack, which will lead to a recursion depth exceeded error on larger inputs.

(define (count-change-true-iterative amount)
  ;; penny is not in the signiture, bacause it equals (- amount
  ;;                                                     (* half-dollar 50)
  ;;                                                     (* quarter 25)
  ;;                                                     (* dime 10)
  ;;                                                     (* nickeli 5))
  (define (count-iter sum half-dollar quarter dime nickeli)
    (cond ((> (* half-dollar 50) amount)
           sum)
          ((> (+ (* half-dollar 50)
                 (* quarter 25)) amount)
           (count-iter sum(+ half-dollar 1) 0 0 0))
          ((> (+ (* half-dollar 50)
                 (* quarter 25)
                 (* dime 10)) amount)
           (count-iter sum half-dollar (+ quarter 1) 0 0))
          ((> (+ (* half-dollar 50)
                 (* quarter 25)
                 (* dime 10)
                 (* nickeli 5)) amount)
           (count-iter sum half-dollar quarter (+ dime 1) 0))
          (else (count-iter (+ 1 sum) half-dollar quarter dime (+ nickeli 1)))))
  (count-iter 0 0 0 0 0))

And can thus handle a calculation like (count-change-true-iterative 3232) though it may take several minutes to do so. ;Value: 76915410