SICP exercise 1.30

From Drewiki

Problem

The sum procedure given in the text in section 1.3.1 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 <??> <??>))

Solution

result is clearly intended to keep a running total of the sum throughout the iteration. We can use lexical scoping to get the value of procedure sum's formal parameter b in the body of the iter procedure, so we don't need to pass it as an argument to iter. Here's an iterative sum procedure:

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

Note that the formal parameter a in the body of procedure iter is a different variable than the formal parameter a in the body of procedure sum!

Here's a test using simpsons-rule-integral from exercise 1.29:

(define (simpsons-rule-integral f a b n)
  (define (inc k) (+ k 1))
  (define (helper h)
    (define (y k)
      (f (+ a (* k h))))
    (define (term k)
      (cond ((or (= k 0) (= k n)) (y k))
            ((even? k) (* 2 (y k)))
            (else (* 4 (y k)))))
    (* (sum term 0 inc n)
       (/ h 3)))
  (helper (/ (- b a) n)))
 
(define (cube x) (* x x x))
 
(simpsons-rule-integral cube 0 1 100)

Output:

0.25