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.

## No comments:

Post a Comment