Problem 31 - コインの両替問題

SICPでやった気がする。

イギリスでは硬貨はポンド£とペンスpがあり，一般的な流通ではこれらの8つの硬貨がある．
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
以下の方法で£2を作ることが可能である．
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
いくらかの硬貨を使って2ポンドを作る方法はいくつあるでしょうか?

再帰で解けるかどうか不安だったけど、なんとかなった。

(define (problem31 c n)
  (cond ((zero? n) 1)
        ((or (negative? n) (null? c)) 0)
        (else
          (+ (problem31 c (- n (car c)))
             (problem31 (cdr c) n)))))

(problem31 '(200 100 50 20 10 5 2 1) 200) ; 73682

やっぱ重いな。

追記

高速化した
- コインの種類が1個。つまり、1 1 1...という連続になったら、必ず1種類と確定出来る。重い処理の殆どが1に偏っているので、これだけで40倍くらい高速化出来た。す・すげぇ。
更に高速化するには？
- 同じ計算を何度も行っているので、メモ化すると相当早くなるはず。