使用MAP/RELAD在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

不使用地图/减少，但迭代也可以避免递归。

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

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

这需要21毫秒的英特尔2.4 GHz

在同一台机器上，减少为61msec。不确定为什么迭代更快。

   (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)))

Answer 3

这将为您提供第一个1000个斐波那契数的向量（大小的 range + 2），处理函数的第二个参数（range）作为柜台：

(reduce 
  (fn [a b] (conj a (+' (last a) (last (butlast a)))))  
  [0 1]                      
  (range 998))