Exercise 1.37: Continued Fraction

Write a procedure to calculate a continued fraction, such as:

In approaching the problem I think of the expression like this:

This lends itself naturally to a recursive definition. "The Rest" is just the next procedure call. The terminating case is when you have called the procedure k times.

I had to define a helper procedure so that I could keep track of the index. The only way I see to avoid this is to define the procedure to take four arguments, like (define cont-frac d n a b), which starts at a and ends at b. Since the exercise specifically asks for a procedure with three arguments, I chose to create a helper function.

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

;; Estimate of golden ratio
(/ 1 (cont-frac (lambda (x) 1.0) (lambda (x) 1.0) 10))

The iterative version is a little harder, but by now I'm getting the hang of this. I know I need a results variable to store the results of my work from one iteration to the next. The steps are

• Start with the final term N_k/D_k
• Check whether you're done.
• If you're not done, the new result is N_k-1 / (D_k-1 + Result_k)
• You're done after you've calculated the step with N₁ and D₁. Repeat until k=0

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

;; Estimate of golden ratio
(/ 1 (cont-frac (lambda (x) 1.0) (lambda (x) 1.0) 10))

---

Update: Fixed an off-by-one error in the iterative version.