SICPの勉強 問題1.17~18

SICP1.2.4の問題1.17と1.18を解いてみる。

とりあえずdoubleとhalveを定義：

(defn double [x]
  (* 2 x))

(defn halve [x]
  (/ x 2))

linear recursiveに書くとこんな感じ：

(defn mul [a b]
  (cond
    (zero? b) 0
    (even? b) (double (mul a (halve b)))
    :else     (+ a (mul a (dec b)))))

末尾再帰が効くようにするなら、1.16と同じ形になる：

(defn mul-iter [a b]
  (loop [b b x 1 y a z 0]
    (cond
      (zero? b)        z
      (< b (double x)) (recur (- b x) 1 a (+ y z))
      :else            (recur b (double x) (double y) z))))

これもmapやiterate、apply +で書けるはず。