SICP Exercise 1.37: Calculating ϕ as a k-Term Continued Fraction

1. An infinite continued fraction is an expression of the form

   f =          N1         
       D1 +       N2      
            D2 +    N3   
                 D3 + …
   

   As an example, one can show that the infinite continued fraction expansion with the N_i and the D_i 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

         N1      
   D1 +    N2   
        ⋱ + NK
             DK
   

   Suppose that n and d are procedures of one argument (the term index i) that return the N_i and D_i 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?
2. 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.

Let's start with the iterative approach for a change...

If we look at the formula for a k-term continued fraction we can see that it looks "rather difficult" to start from the 1^st term and accumulate the result as we go until we reach the k^th term. Using the 1^st terms we could compute N₁/D₁. To then iterate on this value and accumulate the 2^nd terms into this we would need to know both N₁ and D₁ so we could separate out the numerator and denominator and then add N₂/D₂ to the denominator. To accumulate the third term we'd need to know N₁, N₂, D₁ and D₂, and so on. In other words, for any i, 0 < i ≤ k, there is not a separably calculable portion of the k-term continued fraction that contains only the terms 1…i.

What about if we flip it around. We know we can calculate the k^th term without knowing any of the preceeding terms. It's just N_k/D_k. Using this value and the values of N_k-1/D_k-1 we can then calculate the portion of the total sum that is made up of the k^th and (k - 1)^th terms alone. In other words we can calculate:

   Nk-1  
Dk-1 + Nk
      DK

We can then iterate all the way down to the 1^st term, accumulating as we go and produce the result we're after. So:

• We have an iterative step: for any value i, 0 < i ≤ k, divide N_i by the sum of D_i and the accumulated results of the terms i+1 … k.
• We know that we're only accumulating for values in the range 1 … k, so for our initial step (i.e. i = k), we can use 0 as the accumulated results of the terms i+1 … k
• Finally, we know when to terminate: when we get to i = 0 we've accumulated all the terms we need to.

Putting these together we get:

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

Let's now use this to calculate approximations to 1/ϕ. We're asked to try to find the value of k that produces an approximation to 1/ϕ that is accurate to 4 decimal places. 1/ϕ = 2 / (1 + √5) ≈ 0.6180 to four decimal places, so let's start at k = 1 and stop when we find our answer:

> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 1)
1.0
> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 2)
0.5
> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 3)
0.6666666666666666
> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 4)
0.6000000000000001
> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 5)
0.625
> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 6)
0.6153846153846154
> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 7)
0.6190476190476191
> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 8)
0.6176470588235294
> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 9)
0.6181818181818182
> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 10)
0.6179775280898876
> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 11)
0.6180555555555556
> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 12)
0.6180257510729613

So we need k = 12 to get an approximation to 1/ϕ that is accurate to 4 decimal places.

For part (b) we're asked to produce the corresponding iterative or recursive procedure depending upon whether we originally produced a recursive or iterative procedure respectively. Well we produced an iterative procedure to begin with, so we need to produce a recursive procedure here.

Note that we can't directly translate the iterative procedure to a recursive one (i.e. going through the terms in the order k…1) for a similar reason to why the iterative procedure has to go through the terms in that order. For the recursive procedure we want to calculate the i^th term by performing some operation on the next term in the sequence in the order we are traversing it. If we were to follow the same traversal order as the iterative process that would mean that we would want to calculate the i^th term by performing some operation on the (i-1)^th term. But, by the definition of the formula, to calculate the (i-1)^th term we have to first calculate the i^th term, and we would have an infinite regress.

Instead simply notice that the formula for a k-term continued fraction can be described easily as a recursive process: for any i, 0 < i ≤ k, the portion of the formula produced by the i^th to k^th terms can be calculated by dividing N_i by the sum of D_i and the portion of the formula produced by the (i+1)^th to k^th terms. All we need to do is ensure that we terminate the process after we've calculated the k^th term and we're done. We can do this by having the recursion return 0 when i>k:

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