Iterative "counting change" implementation in mit-scheme 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 ((&gt; (* half-dollar 50) amount)
           0)
          ((&gt; (+ (* half-dollar 50)
                 (* quarter 25)) amount)
           (count-iter (+ half-dollar 1) 0 0 0))
          ((&gt; (+ (* half-dollar 50)
                 (* quarter 25)
                 (* dime 10)) amount)
           (count-iter half-dollar (+ quarter 1) 0 0))
          ((&gt; (+ (* 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?
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 (&gt; 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))