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.


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.


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