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

## Contents

## Recursive Version[edit]

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[edit]

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[edit]

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[edit]

;; 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[edit]

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

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