SICP Exercise 1.17
(define (fast-mult a b)
(cond ((= b 0) 0)
((= b 1) a)
((even? b) (double (fast-mult a (halve b))))
(else (+ a (fast-mult a (- b 1))))))
And here’s the recursive process:
(fast-mult 3 7)
(+ 3 (fast-mult 3 6))
(+ 3 (double (fast-mult 3 3))
(+ 3 (double (+ 3 (fast-mult 3 2))))
(+ 3 (double (+ 3 (double (fast-mult 3 1)))))
(+ 3 (double (+ 3 (double (+ 3 (fast-mult 3 0))))))
(+ 3 (double (+ 3 (double (+ 3 0)))))
(+ 3 (double (+ 3 (double 3))))
(+ 3 (double (+ 3 6)))
(+ 3 (double 9))
(+ 3 18)
21