Example: Counting change pp 40-42

前回のTree型の再帰パターン、というか再帰で書かないとわけわからん！という例を解く。
ここでの例題は決められた通貨単位で指定された金額を払うための方法が何通りあるか、というもの。
確かに再帰で考えていくと結構簡単。今注目してる通貨(例えば500円玉)を使い続ける場合と、次の通貨に進んだ（例えば100円玉）場合とでツリーを構成していけば良いのだ。
使ってみて残り金額が0になったら1通り見つけた！　残り金額がマイナスになったらその探索は失敗。また、全ての通貨を見てしまったらその場合も失敗。それ以外の場合はもう一度再帰的に同じことを繰り返す--すなわちツリーの枝わかれをすれば良い。
んー、簡単。だが本当にこれでうまくいくんだろうか…と一瞬思ってしまうところが再帰プログラミングの面白いところ。
飛んでもないステップ数になりそうだが実際にそれをEx1.11でチェックする。

簡単にrecursiveで書いたら効率的に演算する、、、って、脚注のテーブル使う方法ってhaskell方式？
この話、最初読んだときは強制的にiterativeに変換するコンパイラのイメージだったのだけれど。。。

[SICP]Ex.1.11

割愛。３４接点もある。11セント程度ですごいことになったよ。。。

[SICP]Ex.1.12

いわゆるパスカルの三角形

(define (pascal x y)
  (cond ((or (= x 1) (= x y) 1)
        (else (+ (pascal x (- y 1))
                 (pascal (- x 1) (- y 1))))))

こんなんでちゃんと出るから恐ろしい。