Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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.

like image 991
Ruslan Avatar asked Dec 04 '15 18:12

Ruslan


1 Answers

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:

  • Automatic TCO in Clojure (asking whether an automatic facility to make explicit invocation of recur unnecessary is available).
  • Why does TCO require support from the VM? (asking for the basis behind the claim made in the above-quoted clojure.org documentation that automatic TCO cannot be implemented without either JVM support or breaking use of JVM calling conventions and thus harming interoperability).
  • Why can't tail calls be optimized in JVM-based Lisps? (likewise, more generally)
like image 64
Charles Duffy Avatar answered Nov 18 '22 15:11

Charles Duffy