問題 1.11

無職の間にSICPも読んでみる。目標は焦らずしっかりと読む。問題の解答をさらす。解く順番は出来るだけシーケンシャル。

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

Exercise 1.11
A function f is defined by the rule that f(n) = n if n < 3 and f(n) = f(n-1) + 2f(n-2) + 3f(n-3) if n ≧ 3. Write a procedure that computes f by means of a recursive process. Write a procedure that computes f by means of an iterative process.

再帰的プロセスは定義のまま書けばよいので簡単。

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

反復的プロセスで書くには、以前の値を保持する必要がある。今回のケースは３つの値を保持するための変数とカウンタ用の合計４つの変数を使用する。

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

C で書くとこういう感じになる

再帰的プロセス

int f(int n)
{
    if (n < 3)
        return n;
    else
        return f(n-1) + (2 * f(n-2)) + (3 * f(n-3));
}

反復的プロセス

int f(int n)
{
    int a, b, c, x;

    if (n < 3) {
        return n;
    } else {
        for (a = 2, b = 1, c = 0; n >= 3; n--) {
            x = a + (2 * b) + (3 * c);
            c = b;
            b = a;
            a = x;
    }
    return x;
}