# SICP - Solution: Exercise 1.31

##### October 24, 2018

## Exercise 1.31 #

- The sum procedure is only the simplest of a vast number of similar abstractions that can be captured as higher-order procedures. Write an analogous procedure called
`product`

that returns the product of the values of a function at points over a given range. Show how to define`factorial`

in terms of product. Also use product to compute approximations to π using the formula $$\frac\pi4=\frac{2\cdot4\cdot4\cdot6\cdot6\cdot8\cdot\cdots}{3\cdot3\cdot5\cdot5\cdot7\cdot7\cdot\cdots}$$- If your product procedure generates a recursive process, write one that generates an iterative process. If it generates an iterative process, write one that generates a recursive process.

## Solution #

###
Implementing recursive `product`

#

This is straightforward to implement the recursive function `product`

from the `sum`

code:

```
(define (product term a next b)
(if (> a b)
1
(* (term a)
(product term (next a) next b))))
```

###
Implementing `factorial`

in terms of `product`

#

Again, this is quite straightforward:

```
(define (identity x) x)
(define (inc n) (+ n 1))
(define (factorial n)
(product-iter identity 1 inc n))
```

###
Implementing Wallis' product for π in terms of `product`

#

The formula presented in the text is not very clear, but a quick search on wikipedia gives a formula like this:

$$\prod_{n=1}^\infty\left(\frac{2n}{2n-1}\cdot\frac{2n}{2n+1}\right)$$

This formula can be implemented directly using the `product`

function:

```
(define (wallis-product n)
(define (term n)
(* (/ (* 2 n)
(- (* 2 n) 1))
(/ (* 2 n)
(+ (* 2 n) 1))))
(product term 1.0 inc n))
```

One can argument that this is not optimized, since `(* 2 n)`

is computed multiple times. On the other hand it makes the code much easier to check.

###
Implementing iterative `product`

#

This can be done like this:

```
(define (product-iter term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (* a result))))
(iter a 1))
```