CODEWITHSUNDEEP
recursionclojure
Kannan Ramamoorthy
Kannan Ramamoorthy

Reputation: 4190

Trying to understand clojure Fibonacci recursion

I am trying to understand the below program to find the Fibonacci series using recursion in Clojure.

(defn fib
[x] 
(loop [i '(1 0)]
    (println i)
    (if (= x (count i))
        (reverse i)
        (recur 
          (conj i (apply + (take 2 i))))))) // This line is not clear

For ex for a call fib(4) I get the below output,

(1 0)
(1 1 0)
(2 1 1 0)
(0 1 1 2)

Which as per my inference the conj seems to add the value of (apply + (take 2 i)) to the start of the i. But that is not the behaviour of conj. Can someone help me understand how exactly this works?

Upvotes: 0

Views: 88

Answers (2)

Carcigenicate
Carcigenicate

Reputation: 45826

That is the behavior of conj, for lists. conj doesn't always add to the end:

(conj '(1) 2) ; '(2 1)

(conj [1] 2) ; [1 2]

The placement of the added element depends on the type of the collection. Since adding to the end of a list is expensive, conj adds to to front instead. It's the same operation (adding to a list), but optimized for the collection being used.

Upvotes: 2

Alex Ott
Alex Ott

Reputation: 87359

Per Clojure documentation:

The 'addition' may happen at different 'places' depending on the concrete type.

Appending to list happens to beginning of list, appending to vector happens to the end...

See more examples at https://clojuredocs.org/clojure.core/conj

Upvotes: 1

Related Questions