CODEWITHSUNDEEP
recursionclojure
Ruslan
Ruslan

Reputation: 3273

Clojure - using recur vs plain recursive function call

Why does Clojure have the "recur" special form?

When I replace the "recur" with the function itself I get the same result:

(defn print-down-from [x]
  (when (pos? x)
    (println x)
    (recur (dec x))
    )
  )
(print-down-from 5)

Has the same result as

(defn print-down-from [x]
  (when (pos? x)
    (println x)
    (print-down-from (dec x))
    )
  )
(print-down-from 5)

I was wondering if "recur" is just a safety measure so that the compiler will throw an error if a developer happens to use a non-tail recursion. Or maybe it's necessary for the compiler to optimize the tail recursion?

But what I'm wondering most is about any other reasons other than stack consumption.

Upvotes: 15

Views: 4419

Answers (2)

Charles Duffy
Charles Duffy

Reputation: 295500

As explained in the clojure.org page on functional programming:

In the absence of mutable local variables, looping and iteration must take a different form than in languages with built-in for or while constructs that are controlled by changing state. In functional languages looping and iteration are replaced/implemented via recursive function calls. Many such languages guarantee that function calls made in tail position do not consume stack space, and thus recursive loops utilize constant space. Since Clojure uses the Java calling conventions, it cannot, and does not, make the same tail call optimization guarantees. Instead, it provides the recur special operator, which does constant-space recursive looping by rebinding and jumping to the nearest enclosing loop or function frame. While not as general as tail-call-optimization, it allows most of the same elegant constructs, and offers the advantage of checking that calls to recur can only happen in a tail position.

When you don't use recur (or trampoline), your function calls consume stack: Thus, if you ran (print-down-from 100000), you would quickly observe a crash.

Providing this language facility, then, offers several benefits:

  • Contrary to conventional recursive calls (as given in the question's example), using recur does not consume stack.
  • The author knows that TCO is in use (and stack is not consumed), as use in a position where TCO is not possible would cause a compile-time failure. As such, the stack-consumptions characteristics are obvious both to the code's author and its readers, unlike languages with only automatic TCO (where one would need to read carefully -- taking macro expansions into account -- to determine whether a call is genuinely in tail position before knowing whether it is optimized).
  • Compatibility with conventional JVM calling conventions, and thus native interoperability with code written in other JVM-centric languages is preserved.

Finally, for background, see one of several other questions on the topic on StackOverflow:

Upvotes: 17

octopusgrabbus
octopusgrabbus

Reputation: 10695

As I understand it, the loop .. recur uses tail-end recursion, so your program doesn't blow the stack, and regular recursion does not. Some solutions to problems on 4clojure wind up not using loop .. recur, because -- I'm taking an educated guess -- the solution can only be derived using a direct, recursive function call, instead of loop .. recur.

From what I have read, in some of the Clojure books from a few years ago, you should feel free to use loop .. recur.

However, at least from the discussion in those books I have read and from answers I have received to my Clojure questions here in SO, there is some general consensus to try to solve your problem first using constructs like map. If that is not possible, then by all means go ahead and use loop .. recur, and if you do not think there is a possibility of blowing your stack, a direct recursion call.

Upvotes: 0

Related Questions