SICP 練習問題 1.11

べらぼーに時間がかかってしまいましたよ、練習問題の1.11。
でもなんとか自力で解けた（ハズな）ので結構満足。
んでは当時の脳内をトレースして参りましょう。

練習問題 1.11

F(n) = n                          (※ n ＜ 3)
     = F(n-1) + 2F(n-2) + 3F(n-3) (※ 3 ≦ n)

上記の関数を実装する。


【再帰的（非末尾再帰）】
これは特別なひねりなしで実装できた。

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

【反復的（末尾再帰的）】
さて、末尾再帰ですよ。
重要なのは、自身を再帰呼び出しする箇所を一ヶ所にすることだと思う。
このルールを守ることで、tree構造の計算処理にならなくなるので。

とすると、引数として受け取った数値をそのまま次の計算に使用できるようにする必要がある。 じゃ、どうやるか。
オペレーション F(n-1) と F(n-2) と F(n-3) について、既に計算された結果を、 再帰関数 f-1-iter に渡す、と考える。
この関数の定義だと、次のように解釈することにした。

--------------------
・F(n-1) = n_1 大きい
・F(n-2) = n_2　 ↓↑
・F(n-3) = n_3　小さい
--------------------

そうすると、f-1-iter が受け取る引数を n_1, n_2, n_3 とすれば、計算のエッセンスは次のように記述できる。

(define (f-1-iter n_3 n_2 n_1)
  (f-1-iter n_2                           ;n_2を、次の計算のn_3とみなして渡す。
            n_1                           ;n_1を、次の計算のn_2とみなして渡す。
            (+ n_1 (* 2 n_2) (* 3 n_3)))) ;所定の計算式を実行し、新たな項の値を求めてからn_1とみなして渡す。

さて、問題の根幹は上記でOKだと思うので、次に終了条件を考えよう。
この計算を行う時に、再帰的処理の f-0 と同じように呼び出したいとすると、「何番目？」の情報を引数として渡す感じ。
なので、その定義は次のようになる？

(define (f-1 n)
  (if (< n 3) ;;ここはまぁ普通に問題の条件式を実装する。
      n
      (f-1-iter 0 1 2))) ;で、条件に合致しない場合はf-1-iterを呼び出す感じ。

実際の終了処理は、f-1-iter側で決定するのが自然か？
(あんまり推敲してないから別のやり方があるかもしれないけど。)
「何番目？」の情報で終了チェックをするため、「n」をiterに渡してやる。

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

受け取る側としては、「n」が3以下になったら処理の終了とし、 その時の n_1 を返却する？

(define (f-1-iter n_3 n_2 n_1 n)
  (if (< n 3)
      n_1
      (f-1-iter n_2
                n_1
                (+ n_1 (* 2 n_2) (* 3 n_3))
                (- n 1))))

一応これで期待通りの動作をしてくれましたけど、もっときれいに記述できそうですよね～。

また加筆修正しま～す。

－