SICP練習問題1-11

一昨日、昨日と呑み友達の父親の通夜、告別式に行っており、日記の更新ができず。
受付の手伝いや看板持ちに呑み友達連中が駆り出された.

その帰り、他の呑み友達と、うまい博多もつ鍋の店を見つけた.写真をとってくるのをつい忘れていたので、飲み屋レビューはまた次の機会にしておく。
(文書だけではつまらないでしょ？)

今日、今までサボっていたSICPのお話。

再帰と反復について

正確な定義はSICPのP18,19を見てもらうと載っています.

まず再帰について、ざっくり書くと、

○大きな単位から、より小さな単位に手続きを順次適用する。
(上から下に手続きを適用し、「潜っていく」イメージ。)

○最小単位に手続きを適用すると、最小単位の解を得られる。

○最小単位の解を一つ上の単位に戻す。この解を使って一つ上の単位での解を求める.求めたら、さらに一つ上に解を戻す。

○これを繰り返し、最終的に解を求める.

つまり、「大きな単位」から「小さな単位」へと下り、また「大きな単位」に「再」び「帰」る手続きです.

で、反復というのは早い話が「繰り返し」。
「カウンタ」と「しきい値」を別途用意し、カウンタがしきい値に至るまで処理を繰り返すというものです。
(具体例は練習問題1-11)

再帰の利点と欠点をまとめると

【利点】
数式をそのままの形でSchemeに落とせばよいので楽。直感的。

【欠点】
○最下層に行くまで遅延演算するため、解釈系が演算に必要な情報を別途保持する必要がある。そのため、資源をより多く喰う。
○反復に比べると処理速度が遅い。

一方、「反復」は

【利点】
○再帰に比べると、処理速度は早い

【欠点】
○数式をそのまま使えず、別途カウンタやしきい値などを使った反復処理に組み直す必要がある.
○資源の消費量が再帰に比べると少ない。

ということが言える。

手続きとプロセス

「手続き」→書いてあるプログラムそのもの
「プロセス」→解釈系が「手続き」を解釈する過程

の区別はしておかないと。(この手の用語は自覚しないとあやふやに使いがち....)

再帰と反復の腕試しに、練習問題1-11をやってみる。

練習問題1-11.

再帰的手続きでの練習問題1-11.

(define (f n)
    (if (< n 3)
        n
        (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))
    )
)

式をそのままの形で表現すればよいので、簡単。

反復的手続きでの練習問題1-11.

(define (f2 n)
        (if (< n 3)
                n
                (f-iter 2 1 0 n 2)
        )
)

(define (f-iter prev prev2 prev3 max count)
        (if (= max count)
                prev
                (f-iter
                        (+ prev (* 2 prev2) (* 3 prev3))
                        prev
                        prev2
                        max
                        (+ count 1)
                )
        )
)

f-iterのcountの初期値を2にするのがミソ。

たとえば、f(3)〜f(5)までの演算をやってみると
f(3) = f(2) + 2 * f(1) + 3 * f(0)
f(4) = f(3) + 2 * f(2) + 3 * f(1)
f(5) = f(4) + 2 * f(3) + 3 * f(2)
となる。
f(3)〜f(5)をみると「直前に求めた答え」 + 2 * 「一つ前の値」+ 3 * 「ふたつ前の値」
というパターンになっていることがわかる。
つまり、このパターンをある一定の回数繰り返せばよいことになる。