1.37

练习 1.37 a) 一个无穷连分式是一个如下形式的表达式：

$$f = \frac{N_1}{D_1 + \frac{N_2}{D_2 + \frac{N_3}{D_3 + \cdots}}}$$

作为一个例子，我们可以证明在所有的 $N_i$ 和 $D_i$ 都等于1时，这一无穷连分式产生出$1/\phi$，其中的$\phi$就是黄金分割率（见1.2.2节的描述）。逼近某个无穷连分式的一种方法是在给定数目的项之后截断，这样的一个截断称为 k 项有限连分式，其形式是：

$$\frac{N_1}{D_1 + \frac{N_2}{ \ddots + \frac{N_k}{D_k}}}$$

假定n和d都是只有一个参数（项的下标i）的过程，它们分别返回连分式的项$N_i$和$D_i$。请定义一个过程 cont-frac，使得对 (cont-frac n d k) 的求值计算出k项有限连分式的值。

通过如下调用检查你的过程对于顺序的k值是否逼近$1/\phi$：

(cont-frac (lambda (i) 1.0)
            (lambda (i) 1.0)
            k)

你需要取多大的k才能保证得到近似值具有十进制的4位精度？

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

(cont-frac (lambda (i) 1.0)
            (lambda (i) 1.0)
            20)

作为对比，之前使用不动点方式计算的 $1/\phi$ 的结果是：

(define tolerance 0.00001)

(define (fixed-point f x)
    (define (close-enough? v1 v2)
        (< (abs (- v1 v2)) tolerance))
  (define (iteration f x)
    (if (close-enough? x (f x))
        x
        (iteration f (f x))))
  (iteration f x))

(fixed-point (lambda (x) (+ 1 (/ 1 x))) 0.5)

要达到4位的精度，即需要逼近值和真实值的差的绝对值小于 0.0001。

经过实验，当 k 达到 11 时，即可达到4位的精度。

(cont-frac (lambda (i) 1.0)
            (lambda (i) 1.0)
            10)

(cont-frac (lambda (i) 1.0)
            (lambda (i) 1.0)
            11)

b) 如果你的过程产生一个递归计算过程，那么请写出另一个产生迭代计算的过程。如果它产生迭代计算，请写出另一个过程，使之产生一个递归计算过程。

对于所有 $N_i$ 和 $D_i$ 都返回 1 时，就有： $$f = \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \cdots}}}$$ $$f(1) = \frac{1}{1}$$ $$f(2) = \frac{1}{1 + \frac{1}{1}} = \frac{1}{1 + f(1)}$$ $$f(3) = \frac{1}{1 + \frac{1}{1 + \frac{1}{1}}} = \frac{1}{1 + f(2)}$$ $$\cdots$$

a) 展示了递归的过程，以下使用一个迭代过程：

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

    (iter 1 k 1)
)

(cont-frac (lambda (i) 1.0)
            (lambda (i) 1.0)
            20)