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

## Contents |

## Problem A

An infinite continued fraction is an expression of the form

<math>f = \frac{N_1}{D_1 + \frac{N_2}{D_2 + \frac{N_3}{D_3 + \cdots}}}</math>

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

<math>f = \frac{N_1}{D_1 + \frac{N_2}{\ddots + \frac{N_K}{D_K}}}</math>

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

<math>1/\phi</math> 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.