Exercise 1.37 of SICP

2009-07-07

sicp

Exercise 1.37:

a. An infinite continued fraction is an expression of the form

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

As an example, one can show that the infinite continued fraction expansion with the Ni and the Di all equal to 1 produces $ \frac{1}{\phi} $, where $ \phi $ 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

$$ f = \cfrac{N_1}{D_1 + \cfrac{N_2}{{\ddots,} + \cfrac{N_k}{D_k}}} $$

Suppose that n and d are procedures of one argument (the term index i) that return the Ni and Di 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 $ \frac{1}{\phi} $ 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?

(define (cont-frac n d k)
  (define (cf i)
    (if (= i (+ k 1))
      0
      (/ (n i) 
         (+ (d i) (cf (+ i 1))))))
  (if (not (> k 0))
    0
    (cf 1)))

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

.6180555555555556

It takes 11 iterations to get to 4 decimal places within the reciprocal of golden ratio.

$$ \frac{1}{\phi} = 0.618033988 $$

It’s amusing that the LaTeX looks almost identical to the above definition in scheme:

$$ \cfrac{N_1}{D_1 + \cfrac{N_2}{D_2 + \cfrac{N_3}{D_3 +\cdots}}} $$

b. 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.

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

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

.6180555555555556

Contents