News for hackers. Stuff that matters.
Re:What if you couldn’t program with loops? by pcstl on Monday July 15, 2019 @08:55AM (#20440321)
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 recursion.

I am quite often shocked at the number of programmers who, even after years of experience, are not able to use recursion properly. (Not saying this is true of the article's author - but they should have mentioned recursion)

Re:What if you couldn’t program with loops? by sansnomme on Monday July 15, 2019 @10:30AM (#20441151)
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.
Re:What if you couldn’t program with loops? by pcstl on Monday July 15, 2019 @11:29AM (#20441725)
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)
Re:What if you couldn’t program with loops? by Syzygies on Monday July 15, 2019 @11:02AM (#20441458)
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.

Re:What if you couldn’t program with loops? by Retric on Monday July 15, 2019 @11:25AM (#20441688)
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.
Re:What if you couldn’t program with loops? by madhadron on Monday July 15, 2019 @12:04PM (#20442082)
Under the hood it's all conditional jump instructions whether it's tail recursion, loops, or if/else expressions.
Re:What if you couldn’t program with loops? by stcredzero on Monday July 15, 2019 @12:13PM (#20442195)
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.
Re:What if you couldn’t program with loops? by opwieurposiu on Monday July 15, 2019 @01:39PM (#20443218)
There other ways to do it, but they tend to be less efficient.

https://github.com/xoreaxeaxeax/movfuscator

Re:What if you couldn’t program with loops? by ksherlock on Tuesday July 16, 2019 @07:57PM (#20455090)
indexed jump instructions? (where the index is a boolean value corresponding to the if condition...)
Re:What if you couldn’t program with loops? by Retric on Monday July 15, 2019 @10:27PM (#20447027)
Several CPU’s had specific loop instructions. These are slow on x86, but where sometimes useful on other CPU’s.

Though this is half remembered second hand info, so your mileage may very.

Re:What if you couldn’t program with loops? by madhadron on Tuesday July 16, 2019 @02:03AM (#20447820)
You're absolutely right. I'm usually careful about being blinded by current machines. And there are other ways like changing your return stack manually which could be used to loop.

I was trying to express that the various mathematical formalisms we think in are all getting translated to the same machine in the end.

Re:What if you couldn’t program with loops? by jack_h on Monday July 15, 2019 @10:57AM (#20441399)
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.

Re:What if you couldn’t program with loops? by pcstl on Monday July 15, 2019 @11:30AM (#20441737)
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.
Re:What if you couldn’t program with loops? by hombre_fatal on Monday July 15, 2019 @12:35PM (#20442451)
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.

Re:What if you couldn’t program with loops? by brighter2morrow on Monday July 15, 2019 @09:05AM (#20440383)
Any languages don't implement tail-call optimizations though which makes using recursion expensive.
Re:What if you couldn’t program with loops? by asimpletune on Monday July 15, 2019 @09:17AM (#20440477)
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.
Re:What if you couldn’t program with loops? by JD557 on Monday July 15, 2019 @09:25AM (#20440551)
> 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.

Re:What if you couldn’t program with loops? by 0xcde4c3db on Monday July 15, 2019 @09:31AM (#20440608)
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.
Re:What if you couldn’t program with loops? by dleslie on Monday July 15, 2019 @10:25AM (#20441102)
GCC does it automatically, if it's told to optimize at level 2, IIRC.

It's -foptimize-sibling-calls

Re:What if you couldn’t program with loops? by celticmusic on Monday July 15, 2019 @09:50AM (#20440780)
I think you meant Many languages?
Re:What if you couldn’t program with loops? by wolco on Monday July 15, 2019 @11:45AM (#20441908)
recursion can introduce thread killing bugs. Not the first tool to always reach for.
Re:What if you couldn’t program with loops? by pcstl on Monday July 15, 2019 @02:20PM (#20443605)
I never said it was. Just that it should have been mentioned.
Re:What if you couldn’t program with loops? by BubRoss on Monday July 15, 2019 @09:37AM (#20440659)
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.

Re:What if you couldn’t program with loops? by tombert on Monday July 15, 2019 @09:55AM (#20440827)
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.

Re:What if you couldn’t program with loops? by gallerdude on Monday July 15, 2019 @09:57AM (#20440842)
Finding out how to traverse a tree recursively was one of the first great “aha” moments of learning CS.
Re:What if you couldn’t program with loops? by tombert on Monday July 15, 2019 @10:00AM (#20440883)
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.

Re:What if you couldn’t program with loops? by howard941 on Monday July 15, 2019 @10:43AM (#20441257)
Absolutely! As a thought exercise, what sort of non-trivial tree traversal is possible without recursion or looping?

I do use recursion quite a bit but always honoring the JPL coding rule (I can't find it) to put some form of safety fusing in recursive code to avoid inadvertent stack blowouts.

Re:What if you couldn’t program with loops? by lincpa on Monday July 15, 2019 @11:07AM (#20441497)
the Pure function pipe data flow completely conforms to the JPL coding rules.

[The Pure Function Pipeline Data Flow](https://github.com/linpengcheng/PurefunctionPipelineDataflow)

Re:What if you couldn’t program with loops? by AKrumbach on Monday July 15, 2019 @12:01PM (#20442060)
I'd be even more specific than that: understanding the transformation to turn a looping function into a recursive one is the key gateway into being able to comprehend code which uses advanced call-stack manipulation patterns, such as continuations or coroutines. While I hesitate to call such methodologies _simpler_ code, such patterns still will certainly yield more maintainable, reliable code in a strict single-thread language such as Javascript.
Re:What if you couldn’t program with loops? by JustSomeNobody on Monday July 15, 2019 @11:30AM (#20441750)
Remember that not everyone writes code that is designed to run on a machine with lots of RAM. Loops vs Recursion can be a proper engineering trade off when resources are low.
Re:What if you couldn’t program with loops? by tombert on Monday July 15, 2019 @12:51PM (#20442640)
Sure, and I'm not saying you should never write with the loop+stack/list option; right tool, right job.

I'm just saying that there are certain jobs that lend themselves to recursion, and one shouldn't discount it as some purely-academic bit of fun; it's a useful tool to have in your arsenal. If you have reason to worry about a stack overflow or something similar, you probably shouldn't be using recursion for that project; if you're working in an environment where you aren't going to realistically hit those restraints (like in my case), recursion is incredibly valuable sometimes.

That said, even though I'm somewhat of an FP zealot, I think whenever possible (about 9*% of the time), you should use a looping function like `map`, `filter`, `reduce`, or even the Java-style enhanced-for-loop instead of recursion.

Re:What if you couldn’t program with loops? by BubRoss on Monday July 15, 2019 @10:44AM (#20441264)
But what is a 'recursive' data structure? Recursive describes execution, not data. Data in a tree is a heirarchy. Traversing a tree can be done with a stack, since that's what recursion is doing in a less direct way.

Immutable also describes execution and is really just a way of hiding what is really happening under the hood. There isn't anything that recursion enables.

Re:What if you couldn’t program with loops? by tombert on Monday July 15, 2019 @10:55AM (#20441375)
I'm defining "recursive" data structure in basically the same way everyone else does. Here's an example in Haskell:

    data [a] = [] | a : [a]
The element is either empty, or an element and a pointer to another list. This is recursively defined since it points to the source data structure as part of its definition.

I know that traversing a tree can be done with a stack/list; I mentioned that in my response, but the code will typically be bigger and less intuitive; if the data structure is recursive (based on my definition from above), it lends itself to a recursive algorithm.

Sure, under the hood immutable data might be dressing for something at runtime, but the compiler still needs help to use those features; if I want to loop over something and prepend to a list immutably, at least from a code perspective (not the runtime context), I need recursion to properly respect that.

Re:What if you couldn’t program with loops? by cgh on Monday July 15, 2019 @12:51PM (#20442639)
Others have described simple recursive data structures, but a real-world example is in the MTOSI definition of network modeling. Equipment Holders (EH), eg slots, can hold Equipment (EQ), eg cards. EHs can also hold other EHs arbitrarily deep, and EQ can hold EQ as well as EHs. So they are mutually recursive. A standard way to walk such data structures is with mutually recursive functions.

In other words, a natural way to talk about recursive data structures is with recursive functions and this is made more obvious with data structures that are mutually recursive.

Re:What if you couldn’t program with loops? by pcstl on Monday July 15, 2019 @11:32AM (#20441775)
A recursive data structure is a data structure that contains a pointer to another instance of itself. Linked lists, trees, etc.
Re:What if you couldn’t program with loops? by Izkata on Monday July 15, 2019 @01:41PM (#20443239)
Since you listed linked lists first, here's a fun little tidbit from my early days: I couldn't understand that until I first understood the recursive structure of binary trees. Only afterwards did I have the realization "ohhh, it's like a tree with only one child at each node" and suddenly understand the recursive structure in linked lists.
Re:What if you couldn’t program with loops? by skohan on Monday July 15, 2019 @10:03AM (#20440909)
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.

Re:What if you couldn’t program with loops? by pcstl on Monday July 15, 2019 @11:31AM (#20441758)
It's the opposite, actually - every loop can be trivially encoded as recursion, but loops can't encode many common recursive patterns without a lot of work.

Recursion also has the potential to be much clearer than loops in some cases.

Of course, there are also cases where one would do much better to not use recursion, but that's why I think people should know of it.

Re:What if you couldn’t program with loops? by BubRoss on Monday July 15, 2019 @12:25PM (#20442332)
Recursion just gives you a stack data structure by letting you use the call stack. If you have a stack data structure to use explicitly, then recursion doesn't give you anything and takes away the simplicity of being able to see the entire state of the traversal easily since the call stack and traversal state are now intertwined.

You can just take the variables you are passing to each recursive call, put them in a struct, and make a stack of those structs.

Re:What if you couldn’t program with loops? by pcstl on Monday July 15, 2019 @02:19PM (#20443597)
Sure, but depending on the recursion, that technique will vary from "inelegant" to "maddeningly brittle".

It seems like going pretty far just to avoid recursion, unless you're in a resource-constrained domain.

Re:What if you couldn’t program with loops? by BubRoss on Monday July 15, 2019 @11:13PM (#20447215)
There is nothing brittle about it, you push values to the stack instead of passing them to a function (which just pushes them to the call stack). It actually ends up being far less brittle in practice because it is much easier to deal with edge cases and errors. You can break out of a loop much easier than returning different values and having those bubble up.