Implement fibonacci in Clojure using map/reduce

Question

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

I imagine that it will have to be lazy. It's obvious how to do it using recursion or loop/recur.

Answer 1

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]

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

Answer 2

Not using map/reduce, but iterate can avoid recursion too.

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

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

This takes 21ms on an Intel 2.4 Ghz

On the same machine, reduce takes 61msec. Not sure why iterate is faster.

   (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

This will give you a vector of the first 1000 Fibonacci numbers (size of range + 2), handling the second argument of the function (range) as the counter:

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