SICP 問題 1.11

2017/08/15

#sicp

n<3に対してf(n)=n,
n ≥ 3に対してf(n)=f(n - 1) + 2 f(n - 2) + 3 f(n - 3)
なる規則で定義する関数fがある.
再帰的プロセスの方法でf を計算する手続きを書け.
反復的プロセスの方法でfを計算する手続きを書け.

まずは素直に思ったまま書く。

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

思ったまま書くとやはり再帰的プロセスになる。再帰的プロセスのほうが直感的だからね。

次に反復的プロセスに書き直す。ポイントとしては、同じ計算になるところを引数で渡して使い回せば良いと思われる。

(define (f n)
  (define (f-iter a b c count)
    (if (< count 3) a
        (f-iter (+ a (* 2 b) (* 3 c)) a b (- count 1))))
  (cond ((< n 3) n)
        (else
          (f-iter 2 1 0 n))))

f-iterは、今回・1つ前・2つ前の値を引数で受け取る。