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