SICP Exercise 1.30

sicp

Question

The sum procedure above generates a linear recursion. The procedure can be rewritten so that the sum is performed iteratively. Show how to do this by filling in the missing expressions in the following definition:

(define (sum term a next b)
  (define (iter a result)
    (if ⟨??⟩
        ⟨??⟩
        (iter ⟨??⟩ ⟨??⟩)))
  (iter ⟨??⟩ ⟨??⟩))

Answer

Here is my implementation of the solution:

(define (sum term a next b)
  (define (iter a result)
    (if (>= a b)
        result
        (iter (next a) (+ (term (next a)) result))))
  (iter a (term a)))

Let’s re-implement our previous calculation of Simpson’s rule using this new, iterative version of sum:

(define (sum term a next b)
  (define (iter a result)
    (if (>= a b)
        result
        (iter (next a) (+ (term (next a)) result))))
  (iter a (term a)))

(define (cube x) (* x x x))

(define (simpsons_rule f a b n)
  (define h (/ (- b a) n))
  (define (yk k count) (* count (f (+ a (* k h)))))
  (define (term k)
    (cond ((or (= k 0) (= k n)) (yk k 1))
          ((even? k) (yk k 2))
          (else (yk k 4))))
  (* (/ h 3) (sum term 0 inc n)))

(simpsons_rule cube 0 1.0 100)
(simpsons_rule cube 0 1.0 1000)

As we can see, the results are practically the same as in the previous implementation. I don’t know where the tiny variation actually comes from, but I assume it’s a floating point number issue. If somebody knows why this happens, please let me know.

0.25000000000000006
0.25000000000000006