[SICP] 問題 1.11 : f(n)=f(n-1)+2f(n-2)+3f(n-3)

n<3に対して

  f(n)=n, n ≥ 3に対してf(n)=f(n - 1) + 2f(n - 2) + 3f(n - 3)

なる規則で定義する関数fがある. 再帰的プロセスの方法でfを計算する手続きを書け. 反復的プロセスの方法でfを計算する手続きを書け.

Fibonacci数を計算する手続きを参考にして問題文の関数fを定義します.

(require (lib "racket/trace.ss"))

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

(define (f-iter counter x y z)
  (if (= 0 counter)
      z
      (f-iter (- counter 1)
              (+ x (* 2 y) (* 3 z))
              x 
              y)))

(define (f-i n)
  (f-iter n 2 1 0))

;;(trace f-r f-iter)

実行して, 結果を確認します.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (map f-r '(0 1 2 3 4 5 6 7))
(0 1 2 4 11 25 59 142)
> (map f-i '(0 1 2 3 4 5 6 7))
(0 1 2 4 11 25 59 142)
> 

手続きf-rとf-iterをトレースして, 手続きが生成するプロセスを確認します.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (f-r 5)
>(f-r 5)
> (f-r 4)
> >(f-r 3)
> > (f-r 2)
< < 2
> > (f-r 1)
< < 1
> > (f-r 0)
< < 0
< <4
> >(f-r 2)
< <2
> >(f-r 1)
< <1
< 11
> (f-r 3)
> >(f-r 2)
< <2
> >(f-r 1)
< <1
> >(f-r 0)
< <0
< 4
> (f-r 2)
< 2
<25
25
> (f-i 5)
>(f-iter 5 2 1 0)
>(f-iter 4 4 2 1)
>(f-iter 3 11 4 2)
>(f-iter 2 25 11 4)
>(f-iter 1 59 25 11)
>(f-iter 0 142 59 25)
<25
25
> 

トレースの結果から, f-rが再帰的プロセスを生成し, f-iが反復的プロセスを生成していることが分かります.