これも東大の Scheme演習のページから。
cf. Scheme演習 第２回
問1（末尾再帰）
フィボナッチ関数の定義（fib(0)=0、fib(1)=1 …）が載っていて、
この定義をそのまま使って関数 (fib1 n) を作れ。
(define fib1
(lambda (n)
(cond
((= n 0) 0)
((= n 1) 1)
(else (+ (fib1 (- n 1)) (fib1 (- n 2)))))))
gosh> (load "fib1") #t gosh> (fib1 30) 832040 gosh> (fib1 40) 102334155
末尾再帰を使って、n に対して線形の時間で求める関数 (fib2 n) を作れ。その際、ブロック構造を用いて、トップレベルに定義する関数は fib2 のみとせよ。
(define fib2
(lambda (n)
(define fib-iter
(lambda (m a b)
(if (zero? m)
a
(fib-iter (- m 1) b (+ a b)))))
(fib-iter n 0 1)))
gosh> (load "fib2") #t gosh> (fib2 40) 102334155
ふたつのプログラムを同じ引数で実行してみて、時間を比較せよ。さらにその時間の違いの理由について考察せよ。
厳密には時間を計っていないけど、引数が 40 の場合 fib1 は数十秒かかるのに対して、fib2 は一瞬で結果が得られる。理由は簡単、fib1 では再帰のたびに同じ引数に対する計算を何度も行っているのに対して、fib2 では同じ引数に対する計算は1度ですんでいるから。