This is perhaps a slight digression; just an extended expression of pleasure about Clojure’s recur statement. It neatly squashes a bee I’ve had in my bonnet for some years now; if it’s wrong to loathe “tail recursion optimization” then I don’t want to be right.
I acknowledge that
recur isn’t a “statement”, it’s actually a
“special form” which is what languages that don’t want to admit having syntax
call their keywords. But hey, it’s a built-in fixed-syntax thingie that usually
stands on its own line and causes transfer of control to another place in the
program, so for my money it walks like a statement and works like a
Recur Details ·
There’s nothing to it, really. If you’re in a function and you say
(recur arg arg ...) — the number of arguments has to be the same
as the function takes — you restart the function with the new set of arguments
recur. It’s a highly controlled and structured
GOTO. This walks like a loop and smells like a loop, and so,
sensibly enough, there’s another
statement oops special form called
(def factorial (fn [n] (loop [cnt n acc 1] (if (zero? cnt) acc (recur (dec cnt) (* acc cnt))))))
(Gosh, I can’t help but noticing how, in Erlang, you see tons of
functions which exist only to do tail-recursive looping and have names like
whatever_loop. Nudge nudge, wink wink.)
recur is simple, it’s easy to understand, it doesn’t burn
function or loop arguments are still immutable in the context of any single
pass through. Also I find the name “recur” to be an example of engineering
elegance; obviously correct, once you think of it.
I’m amused by the write-ups in the Clojure literature; they all take the
form of “Since Clojure is based on Java, and the JVM doesn’t do tail-call
optimization (how sad) we were forced to provide this
thingie. Sorry ’bout that, and if Java gets its act together, we’ll do tail
But it seems obvious to me that
recur is better than
Why I Hate Tail Call Recursion Optimization ·
It feels like a big fat lie. It looks like a subroutine call, but in the
case where it occurs as the last thing in the routine, it magically, silently,
and automatically gets turned into, now how did I put it? “A highly controlled
If that’s what the programmer wants, then that’s what the programmer should bloody well ask for. I’ve always been irritated by the explanations, in the Erlang and Lisp introductory books, about how you must be careful to ensure that your recursive calls are the last thing executed, and I’ve observed this leading sometimes to some gnarly unintuitive if/else branch placement. Call me old-fashioned, but it just seems wrong when the semantics of two identical function invocations vary wildly as a function of whether there’s an executable statement between the invocation and the function exit.
I Know I Know I Know ·
Every time I write about this I get lectures in the comments, explaining in
a superior tone of voice that I don’t really understand the wonders of the
tail call, and pointing me at
Steele’s 1977 paper (PDF) on the subject.
I think the semantics of computer programs should be made explicit in their
recur does this. It’s a good thing.