SICP問題1.14

今日の問題は、１１セントの両替の場合の数を求める関数の木構造とプロセスのスペースとステップ数を求める問題。

で、関数は

(define (count-change amount)
  (cc amount 5))

(define (cc amount kinds-of-coins)
  (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)))

となるわけなのだが、

木構造はここにはかけないのでとりあえずパス。

で、スペースはnでステップ数はn^2に比例するのかな？

なんとなく違う気がするが、
時間が無いので今日はこれまで。