clojure - 使用 map/reduce 在 Clojure 中实现斐波那契

Question

是否可以使用 Clojure 有效地实现斐波那契数列reduce？“累加器”会包含什么？

我想它必须是懒惰的。很明显如何使用递归或循环/递归来做到这一点。

Answer 1

您可以使用一对连续的斐波那契值作为累加器，如下所示：

(reduce 
  (fn [[a b] _] [b (+ a b)])  ; function to calculate the next pair of values
  [0 1]                       ; initial pair of fibonnaci numbers
  (range 10))                 ; a seq to specify how many iterations you want

=> [55 89]

由于创建了许多中间对并使用多余的范围序列来驱动正确的迭代次数，这并不是特别有效，但从算法的角度来看，它是 O(n)（即与有效的迭代解决方案相同，并且比天真的递归要好得多）。

Answer 2

不使用 map/reduce，但迭代也可以避免递归。

(defn iter [[x y]]
  (vector y (+ x y)))

(nth (iterate iter [0 1]) 10000)

在 Intel 2.4 Ghz 上这需要 21 毫秒

在同一台机器上，reduce 需要 61 毫秒。不知道为什么迭代更快。

   (time (reduce 
     (fn [[a b] _] [b (+ a b)])  ; function to calculate the next pair of values
     [0 1]                       ; initial pair of fibonnaci numbers
     (range 10000)))