Trying to understand clojure Fibonacci recursion

Question

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?

Carcigenicate · Accepted Answer · 2018-05-14 03:40:34Z

2

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.

edited May 14, 2018 at 3:40

answered May 13, 2018 at 18:40

Carcigenicate

46.5k12 gold badges81 silver badges134 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Alex Ott · Accepted Answer · 2018-05-13 18:41:28Z

1

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

answered May 13, 2018 at 18:41

Alex Ott

88.1k10 gold badges110 silver badges157 bronze badges

Collectives™ on Stack Overflow

Trying to understand clojure Fibonacci recursion

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related