From SICP section

1.3.1 Procedures as ArgumentsExercise 1.31 asks us to write a

`product`

procedure (analogous to

`sum`

) that computes the product of a function at points over a given range. We need to show how to define

`factorial`

in terms of the new

`product`

procedure, and use

`product`

to compute approximations to π using the following formula:

Finally, if our

`product`

procedure is recursive, we need to write an iterative version, and vice versa.

Since summing a series and multiplying a series are extremely similar ideas, it's not surprising to find that it's very simple to modify

`sum`

to produce

`product`

. Let's use the recursive version from

exercise 1.29 first.

`(define (sum term a next b)`

(if (> a b)

0

(+ (term a)

(sum term (next a) next b))))

The

`product`

procedure really only needs to perform a different operation and end on a different value than

`sum`

. The last step (when a > b) should be to multiply by 1 instead of adding 0.

`(define (product term a next b)`

(if (> a b)

1

(* (term a)

(product term (next a) next b))))

We can test this out by implementing

`factorial`

in terms of

`product`

using the

`identity`

and

`inc`

procedures that we've used before.

`(define (identity x) x)`

(define (inc x) (+ x 1))

(define (factorial x)

(product identity 1 inc x))

> (factorial 3)

6

> (factorial 4)

24

> (factorial 5)

120

> (factorial 10)

3628800

> (factorial 20)

2432902008176640000

The next test is to approximate π using something called

Wallis' product or the

Wallis Formula. (Lucky for us that mathematicians have already expressed this as the product of a series, saving us the work of coming up with a function for generating the terms.)

We'll multiply the product on the right hand side by the denominator on the left hand side so our procedure will just approximate π directly.

`(define (wallis-pi n)`

(define (term x)

(/ (* 4.0 (square x))

(- (* 4.0 (square x)) 1)))

(* 2.0 (product term 1 inc n)))

> (wallis-pi 10)

3.0677038066434994

> (wallis-pi 100)

3.133787490628163

> (wallis-pi 1000)

3.1408077460304042

> (wallis-pi 10000)

3.1415141186819313

Since our

`product`

procedure is implemented recursively, we need to show an iterative version. We can go back to the iterative

`sum`

procedure for inspiration.

`(define (sum term a next b)`

(define (iter a result)

(if (> a b)

result

(iter (next a) (+ (term a) result))))

(iter a 0))

Again, there are very few changes required to transform this procedure.

`(define (product-iter term a next b)`

(define (iter a result)

(if (> a b)

result

(iter (next a) (* (term a) result))))

(iter a 1))

You can plug

`product-iter`

into the

`factorial`

and

`wallis-pi`

procedures above to verify that they give the same results.

The similarities between our two versions of

`sum`

and

`product`

is no accident. This section of SICP is all about higher-order procedures, so in the next exercise we're going to see how pull the similarities out of these procedures into something even more abstract.

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

The SICP Challenge.