SICP - Solution: Exercise 1.37

October 28, 2018

Exercise 1.37 #

An infinite continued fraction is an expression of the form

$$f=\frac{N_1}{D_1+{\displaystyle\frac{N_2}{D_2+{\displaystyle\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 finite continued fraction k-term finite continued fraction—has the form

$$f=\frac{N_1}{D_1+{\displaystyle\frac{N_2}{\ddots+{\displaystyle\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

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

Solution #

Recursive process continued fraction #

Let’s start with the recursive version, as it is the most straightforward from the definition:

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

Estimating ${1/\varphi}$ #

By running the function with larger number k, we have this result:

Since ${1/\varphi} = 0.618033988749894848204586834365638…$, k must be at least 11 in order to have an approximation accurate to 4 decimal places.

Iterative process continued fraction #

The solution I found is to start at the lowest fraction and work all the way up, keeping the result in result:

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