Exercise 1.37

An infinite continued fraction is an expression of the form

           N₁
f = —————————————————
              N₂
      D₁ + ——————————
                N₃
         D₂+ ————————
              D₃+ ...

As an example, one can show that the infinite continued fraction expansion with the Ni and the Di all equal to 1 produces 1/ϕ, where ϕ is the golden ratio (described in section 1.2.2). One way to approximate an infinite continued fraction is to truncate the expansion after a given number of terms. Such a truncation – a so-called k-term finite continued fraction – has the form

     N₁
————————————
        N₂
D₁ + ———————
         Nκ
    ⋱ + ————
         Dκ

Suppose that n and d are procedures of one argument (the term index i) that return the Nᵢ and Dᵢ of the terms of the continued fraction. Define a procedure cont-frac such that evaluating (cont-frac n d k) computes the value of the k-term finite continued fraction. Check your procedure by approximating 1/ϕ using

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

for successive values of k. How large must you make k in order to get an approximation that is accurate to 4 decimal places?

If your cont-frac procedure generates a recursive process, write one that generates an iterative process. If it generates an iterative process, write one that generates a recursive process.

Here's mine:

a.

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

For k = 12, we approximate 1/ϕ as .62802…, which is accurate to 4 places. For k = 11, we approximate 1/ϕ as .61805̅, which is not.

b.

(define (cont-frac n d k)
  (define (cont-frac-iter n d i quotient) ;; 'addend' might be a better name
    (if (= i 0)
        quotient
        (cont-frac-iter n d (- i 1) (/ (n i) (+ (d i) quotient)))))
  (cont-frac-iter n d k 0))