問題1.17

これは、再帰的なかけ算の問題。再帰プロセスで考えていいそうなので楽*1。

アルゴリズム

• 奇数のとき: a * b = (2a) * (b/2)
• 偶数のとき: a * b = a + a * (b-1)

コード

(define (fast-mul a b)
  (define (double n)
	(* n 2))
  (define (halve n)
	(/ n 2))
  (define (even? n)
	(= (remainder n 2) 0))
  (cond ((= b 0) 0)
		((even? b) (fast-mul (double a) (halve b)))
		(else (+ a (fast-mul a (- b 1))))))

内部関数を定義しちゃってるので、効率はよくないかな。

*1:SICPを勉強しだしてから、反復的にかんがえるよりも、再帰的に考える方が楽になった気がす