Learning Clojure - Part 4 | Finding the nth Fiboncci number

Today I revisited my goal of learning Clojure. If you're not familiar with Clojure, it's descibed by repl.it as

A modern JVM-based Lisp dialect with a focus on immutability

If that description didn't enlighten you, let's just agree that it's a programming language.

Having previously solved Project Euler Problem 1 in Clojure, I decided to give Problem 2 a shot as well.

Problem 2
Even Fibonacci numbers
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

This problem introduces a series of challenges, most notably, being able to find Fibonacci numbers, which this post will focus on.

Since I'm not yet very familiar with Clojure, I'm don't feel confident working iteratively on variables, so my first implementation of a function to find the nth Fibonacci number was a recursive one. Its design is pretty simple:

• If you want to find the first Fibonacci number, the function returns 1.
• If you want to find the second Fibonacci number, the function returns 2.
• If you want to find any other Fibonacci number, the function returns the sum of the the return values from the same function called with an input value decremented with 1 and 2 respectively.

I implemented the function in Clojure like this:

;; Recursive fibonacci
(defn rfib [number]
  (if (= number 1)
    1 
    (if (= number 2)
      2
      (+ (rfib (- number 1)) (rfib (- number 2)))
    )
  )
)
(println (rfib 5)) ;; => 8

The problem with a recursive approach is that it's slow. REALLY SLOW. The online REPL I was using crashed when I tried to find the 20th Fibonacci number. What we would like is to repeatedly find the next number by adding the two previous numbers, without having to recalculate every previous number for every new number. This is where my lack of familiarity with Clojure becomes apparent.

I decided to start small, and solve the problem one step at a time. First, I would like to be able to add an element to a list, or an array, which I believe they're called in Clojure. It turns out that there is a function called conj. I think it means conjoine, whatever that means.

(println (conj [1 2 3] 4)) ;; => [1 2 3 4]

My goal here is to be able to repeatedly add an element to the end of an array, with the value being the sum of the array's last two elements. That means that I have to be able to get the value of the last element in an array. To do this, I use a function called last. I love it when functions are actually have descriptive names.

(println (last [1 2 3 4])) ;; => 4

Next, we need to be able to get the value of the second to last element of a list. To be able to do this, I first use a function called butlast, which returns the whole array except for the last element. Then I use the last function, which we're already familiar with.

(println (last (butlast [1 2 3 4]))) ;; => 3

Now, let's combine what we've learnt to make a function which extends an array with the sum of its last two elements:

(defn sum-end [vector] (conj vector (+ (last vector) (last (butlast vector)))))


(println (sum-end [1 2 3])) ;; => [1 2 3 5]

Now that we have this useful function to find the next Fibonacci number given an array of all the previous Fibonacci numbers, it shouldn't be too difficult to create a function which returns the nth Fibonacci number.

Or so I thought...

I got this far:

(defn fib [number]
  (def vector [1 2])
  (while (<= (count vector) number)
    (println vector)
    (let [vector (sum-end vector)]) ;; I'm not sure about this part.
  )
)

I'll ask a colleague at work tomorrow for some insight. Until then...