# 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 ((> (* 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?

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)

(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))


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