Infinite Continued Fraction - iterative and recursive

Question

Given the following exercise:

Exercise 1.37. a. An infinite continued fraction is an expression of the form

As an example, one can show that the infinite continued fraction expansion with the Ni and the Di all equal to 1 produces 1/, where is the golden ratio (described in section 1.2.2). 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

Suppose that n and d are procedures of one argument (the term index i) that return the Ni and Di 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 1/ 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?

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.

I wrote the following two functions:

Recursive:

(define (cont-frac n_i d_i k)
  (define (recurse n)
    (define (next n) (+ n 1))
    (if (= n k) (/ (n_i k) (d_i k)) 
        (/ (n_i n) (+ (d_i n) (recurse (next n))))))
  (recurse 1))

Iterative:

(define (i-cont-frac n_i d_i k)
  (define (iterate result n)
    (define (next n) (- n 1))
    (if (= n 1) (/ (n_i n) result)
        (iterate (+ (d_i (next n))           
                    (/ (n_i n) result)) (next n))))
  (iterate (d_i k) k))

What do you think of my solution?

Answer 1

Note that your definitions of cont-frac and i-cont-frac accept as arguments the functions n and d, and not n_i or d_i (which, I assume, would be specific values of n and d at index i). I would avoid this confusion by naming the arguments properly.

The definition of i-cont-frac could be improved by rewriting the base case. When the iterant is zero, the result should be zero as well.

One could also abstract out the idea of an initial and a terminal value of the iterant, and the initial value of the result. Here's an implementation of these ideas:

(define (cont-frac n d k)
  (define initial-result 0)
  (define initial-i 0)
  (define terminal-i k)
  (define (recurse i)
    (if (= i terminal-i)
        initial-result
        (let
            ((next-i (+ i 1)))
          (/ (n next-i) (+ (d next-i) (recurse next-i))))))
  (recurse initial-i))

(define (i-cont-frac n d k)
  (define initial-result 0)
  (define initial-i k)
  (define terminal-i 0)
  (define (iterate result i)
    (if (= i terminal-i)
        result
        (let
            ((next-i (- i 1)))
          (iterate (/ (n i)
                      (+ (d i) result))
                   next-i))))
  (iterate initial-result initial-i))

Note the difference in the initial-i, terminal-i and next-i values in these definitions. This is in line with how recursion and iteration work in these functions.

Notice that the recursive definition needs to use let in order to get the next value of i to allow for the 1-indexed nature of the functions n and d and to return the correct value of zero when k is zero. If we assume that k is never zero, we may rewrite a simplified version of the recursive definition like so:

(define (cont-frac n d k)
  (define initial-result 0)
  (define initial-i 1)
  (define terminal-i k)
  (define (recurse i)
    (define (next i) (+ i 1))
    (/ (n i) (+ (d i) (if (= i terminal-i) initial-result (recurse (next i))))))
  (recurse initial-i))

Answer 2

Your solutions look good.

I don't see any significantly different way to do the recursive solution. My preferences for whitespace (mostly concerning the if) are a little different. Also, I wouldn't define a function for next in this situation. If for some reason you don't want to simply put (+ n 1) as an argument a let expression would be more applicable.

(define (cont-frac n_i d_i k)
   (define (recurse n)
     (if (= n k) 
         (/ (n_i k) (d_i k)) 
         (/ (n_i n) (+ (d_i n) (recurse (+ n 1)))) ))
   (recurse 1))

OR

(define (cont-frac n_i d_i k)
   (define (recurse n)
     (if (= n k) 
         (/ (n_i k) (d_i k)) 
         (let ((next_n (+ n 1)))
           (/ (n_i n) (+ (d_i n) (recurse next_n)))) ))
   (recurse 1))

PS - write a function for the nth_odd_square and try this

(/ 4.0 (+ 1 (i-cont-frac nth_odd_square (lambda (i) 2.0) 500000)))