SICP 習題 1.37 解析：無窮連分式的遞歸與迭代實作

無窮連分式簡介

形式：

若所有 Nᵢ = Dᵢ = 1，則值為 1/φ（φ 為黃金分割率）。

有限近似計算

取前 k 項：

遞歸實作

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

從第 1 項遞歸到第 k 項，最後返回 D(k)。

迭代實作

(define (cont-frac-iter n d k)
  (define (cont-frac-iter-inner n d cur-k cur-value)
    (if (= cur-k k)
        (cont-frac-iter-inner n d (- cur-k 1) (d cur-k))
        (if (> cur-k 1)
            (cont-frac-iter-inner n d (- cur-k 1)
                (+ (d cur-k) (/ (n cur-k) cur-value)))
            (/ (n cur-k) cur-value))))
  (cont-frac-iter-inner n d k 0))

從第 k 項反向累積到第 1 項，尾遞歸優化為迭代過程。

驗證：計算黃金分割率

(define (Phi-test k)
  (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) k))
(define (Phi-test-iter k)
  (cont-frac-iter (lambda (i) 1.0) (lambda (i) 1.0) k))

測試發現 k=10 時已達 4 位精度（≈0.6180）。

心得

• 連分式是遞歸定義的天然應用場景。
• 遞歸版直觀但佔棧；迭代版常數空間，適合大 k。
• Scheme 中高階函數（lambda）使傳遞 N、D 函數極為自然。