<< Previous exercise (1.36) | sicp-solutions | Next exercise (1.38) >>
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.
A recursive solution that doesn't require a helper function, but is somewhat awkward:
(define (cont-frac n d k)
(if (= k 0)
0
(/ (n 1)
(+ (d 1)
(cont-frac
(λ (i) (n (+ i 1)))
(λ (i) (d (+ i 1)))
(- k 1))))))
None of the iterative solutions above work because there is no iterative solution. There is no way to accumulate a partial result and pass it forward because the ultimate result will always depend on all terms in a single unwound expression.
This is not apparent due to the test case's n term and d term being unchanging with i. If instead we use the (ex 1.38) e-euler test case we will calculate the incorrect value of 2.50373... rather than 2.71828... I am using:
(define (cont-frac n d k)
(define (frac-iter i result)
(if (> i k)
result
(frac-iter (+ i 1) (/ (n i) (+ (d i) result)))))
(frac-iter 1 0.0))
for the failed case yielding 2.50373... and
(define (cond-frac n d k)
(define (frac-rec i result)
(if (> i k)
0
(/ (n i) (+ (d i) (frac-rec (+ i 1))))))
(frac-rec 1))
for the passed case yielding 2.71828...
The comment above is wrong: to construct an iterative solution, you neek to work backwards, starting with (n k) and (d k) and working your way down with (n (- k 1)) and (d (- k 1)) etc. Here is a minor fix that makes the above solution work:
(define (cont-frac n d k)
(define (frac-iter i result)
(if (= i k)
result
(frac-iter (+ i 1) (/ (n (- k i)) (+ (d (- k i)) result)))))
(frac-iter 0 0.0))
Note that because you start counting at 0, you need to stop the counter at k (not k + 1).
Actually, I think that the recursive version of the first comment and the iterative version of the second comment is already correct. Perhaps the discussion around this exercise is carried to too great a length.
Let's clear it up. The problem asks for layers of fractions, which can be achieved either by a recursive process or by an iterative process. The number of steps would be k. Now, the tricky part is sequence of the count from 1 to k. For the recursive process, the fraction is built, in a way, from the outside to the inside. So the count should go from 1 to k. For the iterative process, however, the fraction accumulates from the inside to the outside, and the count should consequently go from k to 1.
Below is both versions:
(define (cont-frac n d k)
(define (rec x)
(if (> x k)
0
(/ (n x) (+ (d x) (rec (+ x 1))))))
(rec 1))
(define (cont-frac n d k)
(define (iter x result)
(if (= x 0)
result
(iter (- x 1) (/ (n x) (+ (d x) result)))))
(iter k 0))
This sequence from 1 to k or from k to 1 is not important in the context of this exercise, but for situations where the value of n or d depend on the input, the sequence does matter.
Yes. If the value of n or d depend on the input, recursive version should look forward while the iterative version should look backward.