【Scheme】SICP Ex.1.37

Exercise 1.37.  a. An infinite continued fraction is an expression of the form
在SICP練習1.37 中要求寫出連分法的表示，公式如下:

而這個除法式可以用一個遞迴表達式來表示如下：

其中函數 cf(i) 表示連分式的第 i 個項。

因此Scheme程式遞迴寫法如下:

(define (cont-frac n d k)
  (define (frac i)
     (if (< i k)
         (/ (n i) (+ (d i) (frac (+ i 1))))
         (/ (n i) (d i))))
  (frac 1))

迭代寫法如下:

(define (cont-frac-iter n d k)
   (define (frac-iter i result)
       (if (= i 0)
           result
           (frac-iter (- i 1) (/ (n i) (+ (d i) result)))))
   (frac-iter (- k 1) (/ (n k) (d k))))

可以用下面的近似驗證:

> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 100)0.618033988749895

這就是黃金分割比例值。


參考:
1. SCIP 教材