SICP Exercise 1.37

sicp

Question

1​. An infinite continued fraction is an expression of the form

\[f=\frac{N_1}{D_{1}+\frac{N_2}{D_{2}+\frac{N_3}{D_{3}\cdots}}}\]

As an example, one can show that the infinite continued fraction expansion with the \(N_i\) and the \(D_i\) all equal to 1 produces \(1/\phi\), where \(\phi\) is the golden ratio (described in 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

\[f=\frac{N_1}{D_{1}+\frac{N_2}{\ddots+\frac{N_k}{D_{k}}}}\]

Suppose that n and d are procedures of one argument (the term index \(i\)) that return the \(N_i\) and \(D_i\) 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/\phi\) using

(cont-frac (λ (i) 1.0)
           (λ (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?

2​. 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.

Answer

\(1/\phi\) accurate to 4 decimal places would be \(0.6180\). Turns out, we don’t need to iterate a lot to get there, only 12 times.

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

(cont-frac (λ (i) 1.0)
           (λ (i) 1.0)
           12)

Results:

0.6180257510729613

Next, an iterative version of the same function. This gives the exact same results as the function defined above.

(define (cont-frac-iter n d k)
  (define (iterate counter accumulator)
    (cond ((= counter 0) accumulator)
          ((= counter k) (iterate (- counter 1) (/ (n counter) (d counter))))
          (else (iterate (- counter 1) (/ (n counter) (+ (d counter) accumulator))))))
  (iterate k 1))

Actually this is a little awkward since on our first call of iterate, we need to pass some value for accumulator, even though it will be overwritten on the very first iteration anyways. I used 1 here, but we could just as well have written (iterate k 459384).