Generating the Fibonacci Sequence in Clojure

So today I was looking at the problem of generating the fibonacci sequence in Clojure. Figuring out the value of the sequence at a certain value n was simple enough, but the solution to return an entire sequence seemed to elude me. So I did some searching, and it seems like the primary solutions involved the use of lazy-sequences. So I’ve decided to write about these methods as they do provide insight into lazy sequences and recursion in clojure.

(defn simplefib [n]
 (case n
   0 0
   1 1
   (+ (simplefib (- n 1)) (simplefib (- n 2)))
 )
)

(simplefib 10)
; 55

So to get the nth we just have to use the definition of the fibonacci sequence in order to recursively build upwards, starting with the base cases. Now we move onto collecting these elements to return the full sequence up to the nth element.

The algorithms ¹

The lazy sequence

The first method we’re going to look at is possibly the closest and most recognizable to the simple recursive version we just looked at before.

(defn get-fib-seq [x]
  (let [lazy-fib-seq
  ((fn build-fib [a b]
      (lazy-seq (cons a (build-fib b (+ a b))))
  ) 0 1)]
  (rest (take (+ x 1) lazy-fib-seq)))
)

(get-fib-seq 10)
; => (1 1 2 3 5 8 13 21 34 55)

Let’s take a closer look.

1. The crux of the code relies on the definition of lazy-fib-seq
2. We create a recursive function build-fib which takes two values, presenting the F(n - 1)th and F(n - 2)th value, required in the fibonacci calculation.
3. We kick off the function call by calling build-fib on 0 and 1.
4. Each time it concatenates a onto a lazy sequence, and saving the calculation b for a later time. More importantly though, b is defined as a recursive call, providing fresh F(n - 1) and F(n - 2) values for subsequent calculations.
5. So basically what we’re left with is lazy-fib-seq, an infinite sequence of calculations to be performed as we go. Notice that we’re actually building this sequence from the ground up, as we would if we were writing this using a loop in any other language.
6. Finally we return the first x number of values from this lazy-sequence using take (while omitting the inital 0 using rest).

And there you have it.

Using iterate

There’s a function in the core clojure library called iterate. And what it does is that it returns a lazy sequence that repeatedly applies the function f onto a base case a. What you might be left with is the following: [a f(a) f(f(a)) ...]

So again we’d be doing something similar to the previous case, by building the fibonacci sequence from the ground up.

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

(def fib-seq
  (map last (iterate fib-add [0 1]))
)

(take 10 fib-seq)
; => (1 1 2 3 5 8 13 21 34 55)

In this scenario, we first define a function fib-add that takes a vector of two values a and b corresponding the F(n - 1) and F(n - 2) elements respectively. It then returns a new vector with a new set of values for the subsequent call to fib-add. The first will correspond to the current value of b (ie: F(n - 2)), and the second will be the next value in the fib sequence (ie: a + b, or F(n - 2) + F(n - 1)) By iterating fib-add over the base case [0 1], we will get the following lazy-seqeunce (if evaluated). [[0 1], [1 1], [1, 2], [2, 3], [3, 5], ...]

Hence we map over this sequence of vectors, getting the second element from each vector. Finally by using take on this sequence, we can return the first 10 elements from the fibonacci sequence.

The confusing corecursion method ²

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

(take 10 (drop 1 fib-seq))
; => (1 1 2 3 5 8 13 21 34 55)

lazy-cat will concatenate a collection of elements what require future computation. In this case we have this obscure map function that adds two sequences, the original fib-seq and one with the first value popped off. We will see below how this sequence is to be generated. Initially we start with the first two elements of the sequence, being 0 (ie: F(0)) and 1 (ie: F(1)). In which the case the current state of fib-seq will look like the following, where F(2) is the sum of the first two elements. Notice that the computation of F(2) will be tacked onto both fib-seq and (rest fib-seq)

| index                     | 0    | 1    | 2    | 3 | ... |
|---------------------------|------|------|------|---| --- |
| fib-seq                   | 0    | 1    | F(2) |   | ... |
| (rest fib-seq)            | 1    | F(2) |      |   | ... |
| (+ fib-seq (rest fib-seq) | F(2) |      |      |   | ... |


| index                     | 0    | 1    | 2    | 3    | ... |
|---------------------------|------|------|------|------| --- |
| fib-seq                   | 0    | 1    | F(2) | F(3) | ... |
| (rest fib-seq)            | 1    | F(2) | F(3) |      | ... |
| (+ fib-seq (rest fib-seq) | F(2) | F(3) |      |      | ... |

and so on...


| index                     | 0    | 1    | 2    | 3    | ... |
|---------------------------|------|------|------|------| --- |
| fib-seq                   | 0    | 1    | F(2) | F(3) | ... |
| (rest fib-seq)            | 1    | F(2) | F(3) | F(4) | ... |
| (+ fib-seq (rest fib-seq) | F(2) | F(3) | F(4) | F(5) | ... |

and we can evalute these values via the definition. Hence F(2) = 0 + 1 = 1, F(3) = 1 + F(2) = 1 + 1 = 2 and etc…

Finally we can grab the first 10 elements of the fibonacci sequence like before, but first dropping the zero element.

Conclusion

So we’ve seen the different methods in which we could generate the fibonacci squence in clojure, and the importance of lazy sequences have in the language. They allowed us to define the way in which the sequence should be generatedwithout the need for immediate calculations.