sicp-ex-1.37


a) An iterative solution is:

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

It takes on the order of ten terms to be accurate within 0.0001.

b) Making the solution recursive:

 (define (cont-frac n d k) 
    (cond ((= k 0) 0) 
          (else (/ (n k) (+ (d k) (cont-frac n d (- k 1))))))) 

This requires the same number of terms to be accurate within 0.0001.


The recursive solution above is incorrect, it produces a continued fraction with the index values *decreasing* as you descend into each layer of denominators instead of increasing. i.e. : Nk / (Dk + (Nk-1 / (Dk-1 + .... etc. The test does not expose this since the procedures passed to it as n and d always return 1.0 regardless of the (index) values passed to them.

A correct recursive version requires the recursive procedure to be defined inside the cont-frac procedure in order to use an ascending index value, e.g. :

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

Iterative version:

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

This Is incorrect. It needs to do the last division. Like This:

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

Another way to accomplish the same result, is by calling it like this the first time:

 (cont-frac-iter k (/ (n k) (d k))) 

instead of using 0.0. And have it return only `result` at the end.


Actually, correction to your correction. The "last division" is already taken care of with i=1. If you see the text, the definition uses i=1 to i=k. There is no i=0. So by the time i is decremented to 0, result already has the correct answer. You do not need to do any more divisions.


The recursive solution above is incorrect also. It calculate the finite continued fraction from 1 to k-1, instead of k. A minor fix is needed:

 (define (cont-fact n d k) 
   (define (recur i) 
     (if (> i k) 
         0 
         (/ (n i) (+ (d i) (recur (add1 i)))))) 
   (recur 1)) 

Iterative version is the same.


the following is the recursion version:

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

test it:

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

<< Previous exercise (1.36) | Next exercise (1.38) >>