by @yokolet

Level: easy

Loop recur

While for is somewhat like a loop, recur is a real loop in Clojure. recur represents such a remarkable idea that we might even say, “this is Clojure.”

If you have a programming background, you may have heard of tail recursion, which is a major feature of functional languages. This recur special form is the one that implements tail recursion. As the words “tail recursion” indicate, recur must be called in the tail position. In other words, recur must be the last thing to be evaluated.

The syntax of the recur macro is: (recur exprs*)

Look at these simple examples:

user> (defn some-join [coll result]
        (if (= 1 (count coll)) (str result (first coll))
          (recur (rest coll) (str result (first coll) ", "))))

#'user/some-join
user> (some-join ["hello" "world" "love" "coding"] "Words: ")
"Words: hello, world, love, coding"

user> ; when we want to do something just before the recur
user> ; we can use *do*

user> (defn some-join [coll result]
          (if (= 1 (count coll)) (str result (first coll))
            (do
              (println result)
              (recur (rest coll) (str result (first coll) ", ")))))
#'user/some-join
user> (some-join ["hello" "world" "love" "coding"] "Words: ")
Words:
Words: hello,
Words: hello, world,
"Words: hello, world, love, coding"

user> ; however, just for printing out the process, let binding works
user> (defn some-join [coll result]
        (let [_ (println result)]
          (if (= 1 (count coll)) (str result (first coll))
              (recur (rest coll) (str result (first coll) ", ")))))
#'user/some-join
user> (some-join ["hello" "world" "love" "coding"] "Words: ")
Words:
Words: hello,
Words: hello, world,
Words: hello, world, love,
"Words: hello, world, love, coding"

user> ; we attempted the same thing as clojure.string/join function does
user> (str "Words: " (clojure.string/join ", " ["hello" "world" "love" "coding"]))
"Words: hello, world, love, coding"


Even though we can write code without recur, the use of recur is strongly recommended in Clojure because of tail-call optimization (TCO).

Compare a recursive sum-up function and a sum-up-with-recur function that uses recur. The recursive call raises StackOverflowError when summing up to 10000. On the other hand, recur can sum up even 100000. This is why tail-call optimization (TCO) works effectively.

user> (defn sum-up [coll result]
        (if (empty? coll) result
          (sum-up (rest coll) (+ result (first coll)))))

#'user/sum-up
user> (sum-up (range 10) 0)
45
user> (sum-up (range 10000) 0)
StackOverflowError   clojure.lang.ChunkedCons.more (ChunkedCons.java:47)


user> (defn sum-up-with-recur [coll result]
        (if (empty? coll) result
          (recur (rest coll) (+ result (first coll)))))
#'user/sum-up-with-recur
user> (sum-up-with-recur (range 10) 0)
45
user> (sum-up-with-recur (range 10000) 0)
49995000
user> (sum-up-with-recur (range 100000) 0)
4999950000

In every computer language, we can write recursive calls. However, recursion with TCO is a Clojure-specific feature. With TCO, Clojure is good at processing a huge list.

References