SICP Exercise 1.30: Summing Iteratively

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 <??> <??>))

To produce a recursive version of sum we need to start at a. We also need to start with the "null" value for a sum, 0, in case a > b. If that is the case then there will be no terms to sum, and so the result should be 0. This allows us to fill in the gaps in the call to iter:

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

We can also quickly fill in a couple of the other blanks... We know we want to terminate when a > b, and when we terminate we want the value of sum to be the accumulated result:

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

Finally, we need to fill in the recursive call to iter. When we make the recursive call to iter we need to call it with the next of the values we are iterating over. This is generated by (next a). We also need to call it with the updated result, which we produce by adding (term a) to the accumulated result so far. This gives us our final implementation:

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

So let's try it out:

> (sum cube 1 inc 10)
3025
> (sum cube 4 inc 7)
748
> (sum identity 1 inc 10)
55
> (sum identity 4 inc 7)
22