## Note: this wiki is now retired and will no longer be updated!

The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.

# SICP exercise 1.37

The exercise has two parts.

## Problem A

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 section 1.2.2 of the text). 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 (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?

## Solution A

Here's a defintion of cont-frac which generates a recusrive process:

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

$1/\phi$ is approximately 0.6180 (to 4 decimal places). Our tolerance is 0.0001. Let's find the minimum k for which we get a good-enough approximation using this procedure, which returns the first value of k for which the nested procedure close-enough is true:

(define (find-minimum-k n d answer tolerance)
(define (close-enough? guess)
(< (abs (- guess answer)) tolerance))
(define (iter k)
(let ((guess (cont-frac n d k)))
(if (close-enough? guess)
k
(iter (+ k 1)))))
(iter 1))

Now try it using Chicken Scheme 3.1 on a MacBook Pro running Mac OS X 10.5:

(find-minimum-k (lambda (i) 1.0)
(lambda (i) 1.0)
0.6180
0.0001)

Output:

10


It requires 10 terms.

## Problem 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.

## Solution B

The procedure I used in part A generates a recursive process, so here's an iterative version:

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

Test:

(find-minimum-k (lambda (i) 1.0)
(lambda (i) 1.0)
0.6180
0.0001)

Output:

10


It's working.