练习1.18

(define (double x) (* x 2))

(define (halve x) (/ x 2))

(define (mul-iter a b result)
    (cond ((= a 0) result)
          ((even? a) (mul-iter (halve a) (double b) result))
          (else (mul-iter (- a 1) b (+ result b)))))

(define (mul a b)
    (mul-iter a b 0))

构造 $result+a \cdot b$ 不变

如果a为偶数 就把b增倍 把a减半

如果a为奇数 就外加一个b（放在result中） 把a减一

以下是迭代版mul计算100*4的过程

(mul 100 4)
(mul-iter 100 4 0)
(mul-iter 50 8 0)
(mul-iter 25 16 0)
(mul-iter 24 16 16)
(mul-iter 12 32 16)
(mul-iter 6 64 16)
(mul-iter 3 128 16)
(mul-iter 2 128 144)
(mul-iter 1 256 144)
(mul-iter 0 256 400)
400

mul计算4*100的过程是这样的

(mul-iter 4 100 0)
(mul-iter 2 200 0)
(mul-iter 1 400 0)
(mul-iter 0 400 400)

明显比100*4要快上不少

这就提示我们可以改写mul 把a和b中较小的那个作为a

(define (mul a b)
    (if (> b a)
        (mul-iter a b 0)
        (mul-iter b a 0)))

当然 当a和b比较接近的时候 这样的优化并不明显