SICP Exercise 1.37

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/\varphi$, where $\varphi$ 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/\varphi$ using

copy(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/\varphi$ 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.

copy(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:

copy0.6180257510729613

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

copy(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).