14

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.

Ruslan
  • 3,063
  • 1
  • 19
  • 28
  • 3
    Clojure doesn't implement automatic TCO, so your other approach that gives "the same result" is actually consuming stack, so it would fail if you used a large enough number. – Charles Duffy Dec 04 '15 at 18:08
  • ...automatic TCO is incompatible with having Clojure functions follow the same calling conventions as regular Java functions and thus having the fully transparent interoperability that Clojure provides. – Charles Duffy Dec 04 '15 at 18:09
  • See also http://stackoverflow.com/questions/10212928/automatic-tco-in-clojure – Charles Duffy Dec 04 '15 at 18:10
  • Also related: http://stackoverflow.com/questions/23175459/why-does-tco-require-support-from-the-vm – Charles Duffy Dec 04 '15 at 18:10
  • 1
    And further: http://stackoverflow.com/questions/19462314/why-cant-tail-calls-be-optimized-in-jvm-based-lisps – Charles Duffy Dec 04 '15 at 18:11
  • So, using "recur" is just to invoke TCO? Nothing else? – Ruslan Dec 04 '15 at 18:21
  • Yup; it's a human-driven subset of tail call optimization. (I say "subset" because when it's calling a different function rather than calling oneself, `trampoline` is needed). – Charles Duffy Dec 04 '15 at 19:14
  • BTW, it's inaccurate to call TCO a pure performance optimization (as the recent edit does) -- memory consumption, particularly consumption of a bounded resource such as the stack, is a much bigger deal than mere performance. As the clojure.org description says, the difference between constant space execution and consuming stack with each iteration is critical. – Charles Duffy Dec 05 '15 at 21:09
  • @CharlesDuffy thanks, I'll try fix that line. – Ruslan Dec 06 '15 at 08:20

2 Answers2

17

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:

Community
  • 1
  • 1
Charles Duffy
  • 280,126
  • 43
  • 390
  • 441
0

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.

octopusgrabbus
  • 10,555
  • 15
  • 68
  • 131
  • "you're supposed to solve all but the deepest, most difficult problems [without] `loop .. recur`" -- citation needed. – Charles Duffy Dec 04 '15 at 20:31
  • @CharlesDuffy I don't have a citation. It's what I've seen in the various #Clojure books, as well as comments/answers made to questions I've asked here. – octopusgrabbus Dec 04 '15 at 20:34
  • As someone who writes code at a Clojure shop, I'm calling shenanigans. It's not a great code smell -- if there's a solution available that uses `reduce` instead, that's probably more idiomatic [albeit potentially also less performant] -- but it's by no means a facility best avoided outright, and in the real world where function call overhead is nontrivial and measurable, it's often the Right Thing. – Charles Duffy Dec 04 '15 at 20:42
  • @CharlesDuffy I'm not suggesting the use of `loop..recur` be avoided at all costs. I'm suggesting some of the earliest books I read back in 2011 suggested first trying to solve your problem using constructs like `map`. Then, if you needed to, use `loop .. recur`. – octopusgrabbus Dec 04 '15 at 20:47
  • "if there's a solution that uses `reduce` instead, that's probably more idiomatic [albeit potentially less performant]" -- citation needed regarding performance. – schaueho Dec 04 '15 at 20:48
  • @octopusgrabbus, I can agree that one should use `map` or `reduce` in preference. That's not what you said. Adjust your answer to match your comment, and I'm happy with it. – Charles Duffy Dec 04 '15 at 20:53
  • @schaueho, one of the virtues of my choice of weasel words (in this case, "potentially") is that the claim made can be satisfied with an existence proof. One loop with only primitive operations and no function calls in its contents, and we're done -- even if it's faster only before JIT kicks in, that's still a member of the set of "potential" scenarios. Is it worth generating that example? – Charles Duffy Dec 04 '15 at 21:16