SICP Exercise 1.30: Iterative Sums

From SICP section 1.3.1 Procedures as Arguments

Exercise 1.30 asks us to transform the now familiar recursive sum procedure (see exercise 1.29) into an iterative one. We're given the following template to get us started:

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

If you need a refresher on recursive and iterative processes, take a look back at SICP section 1.2.1 Linear Recursion and Iteration. The iterative factorial example given in that section has a lot in common with our template:

(define (factorial n)
 (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
 (if (> counter max-count)
     product
     (fact-iter (* counter product)
                (+ counter 1)
                max-count)))

The key to this procedure is the use of state variables, particularly product, which holds the result of multiplying all the values from 1 to n as the process moves from state to state. In our iterative sum procedure, result will serve as the same kind of state variable, storing the sum of all the terms.

The first two pieces are pretty easy to get. If a is greater than b, we just want to return the result.

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

The next two pieces are the really interesting parts. These are our state variables that make the iterative process work. We need to decide what values to store in a and result for the next iteration to work with. The value passed in for a should be the next term in the series, and the value passed in for result should just add the current term to the result.

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

Finally, we just need to define the starting values for the iterative process. The starting value for a should just be the same a passed in to the sum procedure, and since we're accumulating a sum, the starting value for result should be 0.

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

If you substitute this procedure in for the old one that we used in exercise 1.29, you should see that you get the same results.


Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.