使用map / reduce在Clojure中实现fibonacci [英] Implement fibonacci in Clojure using map/reduce

问题描述

有可能使用 reduce 有效地使用Clojure中的fibonacci系列吗？ accumulator包含什么？

Is it possible to implement the fibonacci series in Clojure efficiently using reduce? What would the "accumulator" contain?

我想这将是懒惰的。

推荐答案

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

You could use a pair of successive fibonacci values as the accumulator, as follows:

(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）（即，与有效的迭代解相同，并且比天真的递归解更好）。

This is not particularly efficient due to the creation of lots of intermediate pairs and use of the superfluous range sequence to drive the right number of iterations, but it is O(n) from an algorithmic perspective (i.e. the same as the efficient iterative solution, and much better than the naive recursive one).

这篇关于使用map / reduce在Clojure中实现fibonacci的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！