SICPの勉強 問題1.37

SICP1.3.3の問題1.37を解いてみる。

recursive process:

(defn cont-frac [n d k]
  (letfn [(rec [i]
    (if (= i k) 
      (/ (n i) (d i))
      (/ (n i) (+ (d i) (rec (inc i))))))]
    (rec 1)))

iterative process:

(defn cont-frac [n d k]
  (loop [i k result 0]
    (if (zero? i)
      result
      (recur (dec i) (/ (n i) (+ (d i) result))))))

idiomatic clojure:

(defn cont-frac [n d k]
  (->> (range k 0 -1)
       (map (juxt n d))
       (reduce (fn [F [N D]] (/ N (+ D F))) 0)))

recursive processのいいところは、元の式を見てすぐイメージする通りに、外から内に記述していけること。つまり、n₁とd₁についてまず考え、そして次にn₂とd₂...n_kとd_kと再帰するたびに内側に潜っていく形になる。しかし、その分外側の処理をスタックに残していくのでメモリ効率は悪い。

内側から解決していけば、つまりi=kからはじめてi=1まで下がっていけば、後回しにする処理なしで再帰できる。あるいはreduceを使って直接再帰することすらなしに記述できる。そのイメージさえつかめてしまえばこのケースでは可読性も何ら劣っていないように思う。

これらを使って１/φの近似値を求めてみる（φは黄金比）:

(cont-frac (constantly 1.0) (constantly 1.0) 10)

結果：

0.6179775280898876

１/φが0.618034あたりなのでk=10で小数点４桁まで正しい結果が出ている。