4 ms·

I agree that recur is nice and explicit about what's happening, but what does "it just seems wrong when the semantics of two identical function invocations vary

• ubernostrum 17y ago
  "The function is either tail recursive or it isn't; it either has extra statements after the recursive call or it doesn't. You can't ever invoke it both ways." I think the thing here is that in, say, Scheme, the performance and actual execution semantics of your function vary wildly depending on how much you mangle your algorithm. If you twist it into a shape that ends with a recursive call, it does one thing; if you don't, it does another thing. This is why tail call is a leaky abstraction and why I generally look down on it (setting aside the fact that the most natural expression of many algorithms often involves other methods of implementation -- truly "naturally" recursive algorithms aren't all that common in my experience).
  • barrkel 17y ago
    Re naturally recursive - it depends on your application domain. If you work with trees all day long, such as in a compiler, templating engine, scene graph, etc. recursion is almost more common than looping.
    • Periodic 17y ago
      Honestly, I feel like recursion is the natural way to express transformations on any nexted data structure (like a list, tree, or graph). I think the major reason that many people don't see these data structures often is because some languages make recursion harder than iteration, so they stick with iteration across arrays and `for` loops. Recursion is really a natural way to express almost any repeated operation on a computer.
  • jfager 17y ago
    Okay, but you're still doing the twisting with recur. The only difference is that the compiler checks that recur is actually in a tail position. That's probably nice to a newcomer, sure, but once you do it a few times, it's pretty simple to tell whether you're making a tail call or not.
    • ubernostrum 17y ago
      I addressed some of this in a comment on the reddit thread: http://www.reddit.com/r/programming/comments/9ye8o/tail_call_amputation/c0f0kcx http://www.reddit.com/r/programming/comments/9ye8o/tail_call...
      • jfager 17y ago
        You're changing the topic of conversation from 'recur' to 'tail-call elimination', but I'll bite. I don't understand your argument. How is the decision to take advantage of tail-call elimination any less a part of an algorithm's implementation than the decision to, say, use a lazy iterator rather than read into an intermediate array? If it's not the best tool for what you're trying to do, certainly, don't use it, but there are plenty of legitimate places where it is needed, so why argue against it?
    • Confusion 17y ago
      It's pretty simple to tell when you are looking at it. However, you may forget/overlook that you are influencing a tail call. If it was optional, I would still opt to use it all the time.
  • deleted 17y ago
    [deleted]
  • kwantam 17y ago
    I think the thing here is that in, say, Scheme, the performance and actual execution semantics of your function vary wildly depending on how much you mangle your algorithm. Precisely the same thing is true with recur in Clojure. The only difference is that once you've mangled your algorithm, you get to proudly signpost it by wrapping it in a recur. It doesn't help the machine at all, it just helps the user. Sounds like a job for... comments! (More specifically, recur only works in situations where TCO would have happened automatically in Scheme---and not even all of those, as other commentors have pointed out. So what you get is a weakened form of TCO that only kind of works and makes your code more verbose for no reason: as I said above, a comment would suffice in these circumstances.)
    • Confusion 17y ago
      A comment wouldn't signal an error if you modified the algorithm and accidentally removed the call from tail position.