用clojure解决 euler problem 1

问题描述：

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

解决方案1：

(defn sum-3-or-5-multiple-below
  [x]
  "If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
   Find the sum of all the multiples of 3 or 5 below 1000."
  (apply +  (filter #(or (= 0 (rem % 3))
                         (= 0 (rem % 5)))
                    (take (- x 1) (iterate inc 1)))))

解决方案2：

(defn sum-3-or-5-multiple 
  [x]
  (loop [current-num 1, sum 0]
    (if (< current-num x)
      (if(or 
           (= 0 (rem current-num 3))
           (= 0 (rem current-num 5)))
        (recur (inc current-num)(+ sum current-num))
        (recur (inc current-num) sum)) sum)))

性能测试：

方案1：

(time (sum-3-or-5-multiple-below 100000))
;"Elapsed time: 157.460515 msecs"

方案2：

(time (sum-3-or-5-multiple 100000))
"Elapsed time: 23.742962 msecs"

分析：

方案1首先用iterate 函数重复加1产生整个序列，然后重序列中筛选所出需要的结果再次组成序列，最后把序列中的结果相加得出结论。所以正如预计的，当数据达到百亿的时候，系统陷入长时间等待中，数据再大，内存可能溢出。用 (range 1 x) 代替

(take (- x 1) (iterate inc 1)) ；性能有所提升，但是还是赶不上方案2的性能。

方案2使用了clojure中的尾递归优化技术。参数current-num初始值是1，sum初始值是0，sum用来保存每次递归的累积结果。每次递归，只与上一次递归的结果相关，因此上上一次递归的数据可以垃圾回收，不会造成内存溢出。