読者です 読者をやめる 読者になる 読者になる

Arantium Maestum

プログラミング、囲碁、読書の話題

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 +で書けるはず。