SICP フィボナッチ数列
フィボナッチ数列
再帰的手続きでフィボナッチ数列を計算する関数を定義すると下記のようになる。
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))
しかしこのパターンだと、例えば (fib 5) を求めるのに (fib 4) と (fib 3) を計算する。
さらにその (fib 4) を求めるのに (fib 3) を計算するため、かなり効率が悪い。
上記を反復的手続きで書き直すと下記になる。
(define (fib n)
(fib-iter 1 0 n))
(define (fib-iter a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1))))
例では上記のように書いてあったけれど、きっと fib でラップするのが良いのだと思う。
(define (fib n)
(define (fib-iter a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1))))
(fib-iter 1 0 n))
fib-iter は何をやっているのかというと、フィボナッチ数例は指定した数の前2つの数(e.g. 5を指定した場合は4つ目と3つ目)を足せばよいので、a が fib(1) ,b が fib(0) とし、そこから count が 0 になるまで足し続けていけば、何度も同じものを計算する必要がなくなる。
反復的な方は確かに計算量は少なくて済むけれど、直感的ではなくわかりにくいのがデメリット。
慣れの問題なのだろうけれど。