SICP: Exercise 1.11

関数

$$ f(n) = \begin{cases} n & \text{if \(n < 3\)} \\ f(n - 1) + 2f(n - 2) + 3f(n - 3) & \text{if \(n \geq 3\)} \end{cases} $$

を計算する手続きを、再帰的処理と繰り返し処理で書く問題。

再帰的処理

これはそのまま

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

で良いと思う。

繰り返し処理

状態変数とその初期値を \(a = f(2) = 2,\ b = f(1) = 1,\ c = f(0) = 0\) とする。状態の遷移に伴って以下の代入を行う。

• \(a \leftarrow a + 2b + 3c\)
• \(b \leftarrow a\)
• \(c \leftarrow b\)

初めは

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

と書いたのだけれど、(*) の部分が余分なのと、\(n = 2\) のときも \(f(3)\) を計算してしまっているところが冗長。

「sicp-ex-1.11 - Community-Scheme-Wiki」によると、\(n < 3\) での \(f(n + 1),\ f(n + 2)\) の計算を回避できるらしい。載っていたものの手続き名を変えたのが次のコード。

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

イテレータの呼び出し回避の仕方が洗練されていて良い。

確認

gosh> (for-each (lambda (x)
.....             (print (f-1-11-r x) ", " (f-1-11-i x)))
.....           '(0 1 2 3 4 5 6 7 8 9))
0, 0
1, 1
2, 2
4, 4
11, 11
25, 25
59, 59
142, 142
335, 335
796, 796
#<undef>

ということで、どちらの処理でも同じ値になるようだ。