04/06/09 14:51
末尾再帰であらわしたコードも見かけましたが、わかりにくさでは似たようなものです。と言うか、これは手続き型のロジックを末尾再帰に無理に書き換えただけだと思います。
(define (fibo num)
(let loop ((num num)
(p2 1)
(p1 1))
(cond ((= num 0) 1)
((= num 1) 1)
((= num 2) (+ p2 p1))
(else (loop (- num 1) (+ p2 p1) p2)))))
もしかして、（よく知らない）遅延評価を使えばよいのかと思い、頭の悪いコードを
書いてみましたが、かえって遅くなるだけでした。
(define (fib3 x)
(if (< x 2)
1
(+ (force (delay (fib3 (- x 1)))) (force (delay (fib3 (- x 2)))))))
遅延評価に関して、Shiro さんのところも見てみたのですが、
URLﾘﾝｸ(www.shiro.dreamhost.com)
これも結局、手続き型と同じ、小さい項をまず計算して、徐々に大きい項を求めていく
やり方でした。定義がそのままコードになるような書き方ではないと思います。
ということで、質問をもう一度まとめますと、
定義がそのままコードになるような書き方で、fibonacci 数列の一般項を求める関数の
計算量を減らすことはできないでしょうか？
以上です。どうかよろしくお願いいたします。