Scheme演習第2回-問1

一昨日に引き続きScheme演習の問題を解いてみる。

問１（末尾再帰）

fibonacci 関数は次のように定義される。
（ここに定義の図）

• この定義をそのまま使って関数 (fib1 n) を作れ。
• 末尾再帰を使って、n に対して線形の時間で求める関数 (fib2 n) を作れ。その際、ブロック構造を用いて、トップレベルに定義する関数は fib2 のみとせよ。
• ふたつのプログラムを同じ引数で実行してみて、時間を比較せよ。さらにその時間の違いの理由について考察せよ。

Scheme演習 第２回

とりあえず、3つめの時間の比較は次回以降にして、今回はfib1とfib2のみ作った。

(define (fib1 n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        ((>= n 2) (+ (fib1 (- n 1)) (fib1 (- n 2))))))

(define (fib2 n)
  (define (fibin n a b)
    (cond ((= n 0) b)
          ((= n 1) (+ b a))
          ((>= n 2)
           (fibin (- n 1) b (+ a b)))))
  (fibin n 1 0)
)

いくつか値を入力してみたところ、正常に動作しているようだ。
今日はここまで。