6 ms·

While the article is a cute way to introduce the loop body extraction refactoring, I think it is a disservice to talk about not using loops without mentioning r

• brighter2morrow 7y ago
  Any languages don't implement tail-call optimizations though which makes using recursion expensive.
  • asimpletune 7y ago
    Pretty easy to implement tail recursion though. Sometimes it’s hard to know if a language that automatically compiles to tail recursion will even always do it.
    • JD557 7y ago
      > Sometimes it’s hard to know if a language that automatically compiles to tail recursion will even always do it. I wish more languages that do not always compile to tail recursive methods had something similar to Scala's `@tailrec` annotation (which forces the compilation to fail if the tail calls cannot be optimized). It's not a very elegant solution, but at least it works.
    • 0xcde4c3db 7y ago
      I even convinced a C++ compiler (don't recall whether it was g++ or clang++; it might have been during a FreeBSD fling) to do TCO at one point, but I don't remember exactly how I did it and don't think the requirements are documented anywhere. It probably involved functions declared "static" (i.e. internal linkage) and with the same signature.
      • dleslie 7y ago
        GCC does it automatically, if it's told to optimize at level 2, IIRC. It's -foptimize-sibling-calls
  • celticmusic 7y ago
    I think you meant Many languages?
• BubRoss 7y ago
  Recursion is either an abstract way to create a loop or a way to use the call stack as a stack data structure. There isn't really a good reason why it needs to be part of a programmer's toolbox. I think the clever nature of recursion is what has made it into something that some programers think is a better way to traverse a data structure, but I think it is often difficult to justify. Even trees can be traversed with a stack of the current state. If something goes wrong, checking the traversal stack is much easier than a runaway call stack.
  • skohan 7y ago
    While it doesn't find it's way into my everyday programming so often, I think recursion does serve a pedagogic purpose if nothing else. Just like learning a bit of Lisp or Prolog, having the "click" moment when first learning about recursion can be really helpful in building intuitions about programming in general.
  • tombert 7y ago
    I completely disagree. For handling recursive data structures, recursion will lead to shorter, simpler code than trying to hack something together with a loop and a custom stack object. While I agree that some of the more dogmatic FP people acting like recursion is the best thing ever might be a bit overstated, I think it's short-sighted to say that "There isn't really a good reason why it needs to be part of a programmer's toolbox". Not to mention, without using recursion, there's no direct way of dealing with purely immutable data structures. You're going to be stuck creating some kind of mutable reference to serve as a counter to a loop, or to append to a list.
    • gallerdude 7y ago
      Finding out how to traverse a tree recursively was one of the first great “aha” moments of learning CS.
      • tombert 7y ago
        About two years ago, I had to (sort of accidentally) create a DSL out of JSON that emitted SQL. My first attempt was trying to hack something together with a bunch of arrays and hashmaps, but I realized that since there's no real "limit" to how nested SQL can be, that that wouldn't work. I scrapped what I was working on, and started over, fully utilizing recursion, and it led to substantially shorter code, that didn't perform measurably slower, and let me handle the full SQL spec correctly. Sadly, I moved off that project, and the person who inherited it didn't understand recursion very well, and rewrote it without recursion, and ended up making it not able to handle the full spec.
• sansnomme 7y ago
  Problem is, tail recursion isn't always particularly elegant and requires a lot more effort when pandering to the compiler (Exhibit A: the factorial example, naive recursive vs tail recursive) that the result is usually harder to follow than one with an explicit stack or queue. Also, some data structures like trees are explicitly stateful no matter how you transform it so they can't be optimized into a tail recursive form at all; I am not sure though in this case if it's clearer to manage the stack directly or to hope that the compiler would optimize it into the most efficient form.
  • pcstl 7y ago
    I never said people should always use recursion. It's just that it's a technique that's useful to have up your sleeve unless you are working in constrained domains (embedded comes to mind)
• jack_h 7y ago
  Honestly at this point in my career I'd have to spend some time remembering how to use recursion properly. I'm also in the embedded realm where I've encountered C compilers that will throw an error if you try to use recursion. I understand your point main point, but not everyone is allowed to even use recursion.
  • pcstl 7y ago
    My point is that people should at least know the basics of recursion. Mentioning "programming without loops" without even mentioning that recursion is an option in that specific case seems neglectful to me.
    • hombre_fatal 7y ago
      I wouldn't go that far. This post is basically newbie-fodder, seemingly from someone more towards that end of the spectrum than the other. Seems unfair to encumber them with expectations on what they thought was a helpful post for beginners grappling with "so, what exactly do I abstract?" It's really just a small tutorial on DRY and finding repetition that you can extract. HN upvoted it because its provocative title makes HNers think of things like recursion and jmp which we can talk about in the comments.
• Syzygies 7y ago
  Never forget that cultural differences look odd in either direction. My favorite passage from "Structure and Interpretation of Computer Programs": > One reason that the distinction between process and procedure may be confusing is that most implementations of common languages (including Ada, Pascal, and C) are designed in such a way that the interpretation of any recursive procedure consumes an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, iterative. As a consequence, these languages can describe iterative processes only by resorting to special-purpose “looping constructs” such as do, repeat, until, for, and while. The implementation of Scheme we shall consider in Chapter 5 does not share this defect. It will execute an iterative process in constant space, even if the iterative process is described by a recursive procedure. An implementation with this property is called tail-recursive. With a tail-recursive implementation, iteration can be expressed using the ordinary procedure call mechanism, so that special iteration constructs are useful only as syntactic sugar.
  • Retric 7y ago
    From the other side, tail call recursion is often actually implemented as a loop by the interpreter. Effectively, making many recursive programs just a different way to write a loop.
    • madhadron 7y ago
      Under the hood it's all conditional jump instructions whether it's tail recursion, loops, or if/else expressions.
      • stcredzero 7y ago
        Is there an alternative to conditional jump instructions? What would a such a computer look like? Maybe such a computer exists, but it's hard for us to see it, because we've been drawn into thinking along Von Neumann machine lines.
        • opwieurposiu 7y ago
• wolco 7y ago
  recursion can introduce thread killing bugs. Not the first tool to always reach for.
  • pcstl 7y ago
    I never said it was. Just that it should have been mentioned.