練習問題 1 (解答例)

• 素直に再帰的定義を用いると、以下の様に定義できる( n = 0, 1 を誤魔化した)

  (define (fib n)
      (if (> n 1)
  	(+ (fib (- n 1)) (fib (- n 2)))
  	n))
  

• 末尾再帰をもちいる為に、 fib-iter をもちいる。 fib-iter は、 引数として i, n, fib(i), fib(i-1) をあらわす変数をもっている。

  (define (fib-iter i n fib-0 fib-1)
      (if (= i n)
  	fib-0
  	(fib-iter (+ i 1) n (+ fib-0 fib-1) fib-0)))
  
  (define (fib2 n)
      (if (> n 1)
  	(fib-iter 1 n 1 0)
  	n))
  

(define (mygcd n m)
   (if (= (remainder n m) 0)
       m
       (mygcd m (remainder n m)))))

;;; 割算 2 回するのが嫌なら
(define (mygcd2 n m)
   (mygcd2-body n m (remainder n m)))

(define (mygcd2-body n m k)
   (if (= k 0)
       m
       (mygcd2 m k)))

;;; 本当は、4. で教える let を使ってこんな感じ
(define (mygcd3 n m)
   (let ((k (remainder n m)))
      (if (= k 0)
          m
          (mygcd3 m k))))