SICP - Solution: Exercise 1.31

October 24, 2018

Exercise 1.31 #

1. 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}$$
2. 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) (* (term a) result))))
  (iter a 1))