CODEWITHSUNDEEP
recursionclojure
Cafe Feed
Cafe Feed

Reputation: 13

4clojure #57 - Simple Recursion

I am going through 4clojure problems and I cannot figure why following code is working

user=> ((fn foo [x] (when (> x 0) (conj (foo (dec x)) x))) 5)
(5 4 3 2 1)

I understand that (foo (dec x)) has to be treated as a PersistentCollection for this to work but what is going on there is a mystery. Any insight why it is working, and why in this order will be appreciated.

Upvotes: 1

Views: 162

Answers (2)

Leonid Beschastny
Leonid Beschastny

Reputation: 51500

Let's have a closer look at your code example. Basically, it's just a function call (foo 5) with the following foo function:

(defn foo [x]
  (when (> x 0)
    (conj (foo (dec x)) x)))

When you call foo with any non-positive value of x it returns nil. Otherwise it return a result of conjoining x to the result of calling (foo (dec x)).

So, calling (foo 2) is a rough equivalent of the following code:

(conj (conj nil 1) 2)

The thing that may confuse you is conj behavior with nil value passed as its first argument.

conj threats nil as an empty list (), so (conj nil 1) produces the same result as (conj () 1). This behavior is documented in conj docs:

=> (doc conj)
(doc conj)
-------------------------
clojure.core/conj
([coll x] [coll x & xs])
  conj[oin]. Returns a new collection with the xs
    'added'. (conj nil item) returns (item).  The 'addition' may
    happen at different 'places' depending on the concrete type.

The other thing that may confuse you is the order of elements in the resulting list. conj is designed to add new element to the PersistentCollection in the most efficient way. In case of lists conj adds new element to the beginning of the original list:

=> (conj '(1) 2)
(2 1)

Upvotes: 6

Michiel Borkent
Michiel Borkent

Reputation: 34870

Let's break this down:

(foo 5) ;;=>
(conj (foo 4) 5) ;;=>
(conj (conj (foo 3) 4) 5) ;;=>
...
(conj (conj (conj (conj (conj nil 1) 2) 3) 4) 5)
;; (conj nil 1) == '(1), so:
;;=>
(conj (conj (conj (conj '(1) 2) 3) 4) 5)
;; conj-ing adds to the head of the list
;;=>
(conj (conj (conj '(2 1) 3) 4) 5)
;;=> 
(conj (conj '(3 2 1) 4) 5)
...
;;=> '(5 4 3 2 1)

Upvotes: 3

Related Questions