练习1.17

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

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

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

$a \cdot b = \left\{ \begin{array}{ll} (halve\ a) \cdot (double\ b),&\text{a is even}\\ b+(a-1) \cdot b,&\text{a is odd} \end{array} \right.$

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

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