Clojure Programming/Examples/Lazy Fibonacci

A function which lazily produces Fibonacci numbers:

(def fib-seq 
  ((fn rfib [a b] 
     (lazy-seq (cons a (rfib b (+ a b)))))
   0 1))
user> (take 20 fib-seq)
(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)

Recursive Version

A version with recursion on data, not functions. see http://en.wikipedia.org/wiki/Corecursion :

(def fib-seq
     (lazy-cat [0 1] (map + (rest fib-seq) fib-seq)))

user> (take 20 fib-seq)
(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)

A different recursive version, making use of the reductions function. ... Does this work? NO. Seems a fake. See discussion.

(def fib-seq
     (cons 1 (reductions + (first fib-seq) fib-seq)))

user> (take 20 fib-seq)
(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)

Properly Scoped Version

There might be a problem in the precedent versions : they create fibonacci lazy-sequences that are bound to top level vars. And as such they are not garbage collected, and if used to compute a very long sequence, will consume a lot of heap. It could be smarter to define fib-seq as a no-arg function that will return a lazy-seq on demand. Then the lazy seq could be put by the caller in the appropriate scope (hopefully not the top level scope) :

(defn fib-seq []
  ((fn rfib [a b] 
       (cons a (lazy-seq (rfib b (+ a b)))))
    0 1))

user> (take 20 (fib-seq))
(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)

Using iterate

We can use iterate to generate pairs of [a b] and then take the first of each one.

(defn fib-step [[a b]]
  [b (+ a b)])

(defn fib-seq []
  (map first (iterate fib-step [0 1])))

user> (take 20 (fib-seq))
(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)

This example also uses destructuring.

Recursive Fibonacci with any start point and the amount of numbers that you want

;; note that your 'start' parameter must be a vector with at least two numbers (the two which are your starting points)
(defn fib [start range]                                                                                                                                                                                                                    
  "Creates a vector of fibonnaci numbers"                                                                                                                                                                                                  
  (if (<= range 0)                                                                                                                                                                                                                         
    start                                                                                                                                                                                                                                  
    (recur (let[subvector (subvec start (- (count start) 2))                                                                                                                                                                               
                x (nth subvector 0)                                                                                                                                                                                                        
                y (nth subvector 1)                                                                                                                                                                                                        
                z (+ x y)]                                                                                                                                                                                                                 
             (conj start z))                                                                                                                                                                                                               
           (- range 1))))

Self-Referential Version

Computes the Fibonacci sequence by mapping the sequence with itself, offset by one element.

(def fib (cons 0 (cons 1 (lazy-seq (map + fib (rest  fib))))))