exercise-1.14.scm

#lang planet neil/sicp

; Exercise 1.14 Draw the tree illustrating the process generated by the
; count-change procedure of section 1.2.2 in making change for 11 cents. What
; are the orders of growth of the space and number of steps used by this
; process as the amount to be changed increases?

; (count-change 11)
; process tree branches off to the left to calculate the first operand in the +
; operation (spawning more branches until it reaches the amount == 0 or the
; (amount < 0 || kind-of-coins == 0) condition).

; num calls needed:
; > (count-change 1)   Calls: 11
; 1
; > (count-change 5)   Calls: 30
; 2
; > (count-change 10)  Calls: 71
; 4
; > (count-change 11)  Calls: 126
; 4
; > (count-change 25)  Calls: 375
; 13
; > (count-change 50)  Calls: 1946
; 50
; > (count-change 100) Calls: 17445
; 292
(define (count-change amount)
  (define return (cc amount 5))
  (display "Calls: ") (display calls) (display "\n")
  return)

(define calls 0)

(define (cc amount kinds-of-coins)
  (set! calls (inc calls))
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                     (- kinds-of-coins 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins)))))

(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))