Exercise 1.31 of SICP

Exercise 1.31:

a. 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{\pi}{4} = \frac{2\cdot4\cdot4\cdot6\cdot6\cdot8\cdots}{3\cdot3\cdot5\cdot5\cdot7\cdot7\cdots} $$

b. 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.

Part A

Notice that the product function looks almost the same as sum. The only things truly different are the multiplication operation and the base case being multiplicative identity. factorial doesn’t require much except the identity function and a trivial next function. It’s easier to think about Wallis Product product if it’s written slightly differently:

$$ \frac{\pi}{4} = \frac{2}{3} \cdot \frac{4}{3} \cdot \frac{4}{5} \cdot \frac{6}{5} \cdot \frac{6}{7} \cdot \frac{8}{7} \cdots $$

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

(define (factorial n)
  (define (identity x) x)
  (define (next x) (+ 1 x))
  (product identity 1 next n))

(define (wallis n)
  (define (next n) (+ n 1))
  (define (term-num i) (if (even? i) (+ i 2) (+ i 1)))
  (define (term-den i) (if (even? i) (+ i 1) (+ i 2)))
  (define (fraction i) (/ (term-num i) (term-den i)))
  (* 4.0 (product fraction 1 next n)))

> (wallis 5)
2.9257142857142857

> (wallis 50) 
3.1719440917427058

> (wallis 500) 
3.1447232866889245

> (wallis 5000) 
3.1419067029355268 

> (wallis 10000) 
3.1417497057380523

While the results do tend to \( \pi \) they do so very slowly.

Part B

This is the iterative version of product. It looks similar to the iterative version of sum.

(define (wallis n)
  (define (next n) (+ n 1))
  (define (term-num i) (if (even? i) (+ i 2) (+ i 1)))
  (define (term-den i) (if (even? i) (+ i 1) (+ i 2)))
  (define (fraction i) (/ (term-num i) (term-den i)))
  (* 4.0 (product-iter fraction 1 next n)))

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