1.17|

$ cd ~

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