4 ms·

> I think you're putting far too much trust into "I haven't seen" and not considering the fact that there is more to see. No, I was being cheeky. The fact that

by dahart 2y ago

> I think you're putting far too much trust into "I haven't seen" and not considering the fact that there is more to see. No, I was being cheeky. The fact that recursion can always be transformed into iteration has been proven. There is no such thing as a “procedure that can’t run without recursion”, which I assumed you already knew, and you might want to keep in mind if you want to keep defending recursion. So do you have any real-world examples where recursion is preferred? This sub-thread started because you were taking umbrage with my claim that recursion is for education and not often used in production code. So far your examples are proving my point, 100% of your examples are classroom problems and not things people need in practice. List reversing might be the most common, and it’s very rare for someone to need to implement it (languages and libraries usually provide it), and far rarer still to need to implement it recursively in practice. Factorial of large numbers and Ackermann function are purely academic exercises.

YeGoblynQueenne 2y ago
>> There is no such thing as a “procedure that can’t run without recursion”, which I assumed you already knew, and you might want to keep in mind if you want to keep defending recursion. There is such a thing. Non-primitive recursive functions can't be converted to iteration. I'm sorry but where did I give examples that are "100% classroom problems"? I gave examples of production code that use Prolog, therefore recursion since Prolog has no iteration constructs: the three jobs in the industry I've held, and the airline software from Sicstus. I can also add IBM's Watson (it used Prolog), Datalog databases (recursion is the point), and the SWI-Prolog website which is running on an http server implemented in Prolog (they call that "eating their own dogfood"). Those are all things that people need in practice and not "classroom problems". There's plenty more Prolog code running in the wild but obviously I don't know every program anyone has ever written using Prolog. There's also code in Answer Set Programming (e.g. I'm aware of planners for robotics applications), Haskell (e.g. xmonad, a windows manager in Haskell) and plenty of code people write in Scheme, Scala, etc Lisps, that also don't have iteration constructs. There's plenty of recursion in "real world" and "production" situations. But I get the feeling you don't work with it, so you just don't believe it exists. That's not a great way to reason about things.
- dahart 2y ago
  > Non-primitive recursive functions can’t be converted to iteration. That’s not true, I think you’re misunderstanding the article you linked to. Primitive recursive functions require fixed bounds, but that is not the same thing as all iteration. The Church-Turing thesis proves that anything you call recursion can be iterated. > I'm sorry but where did I give examples that are "100% classroom problems"? I answered that question in the comment you replied to. > But I get the feeling you don't work with it, so you just don't believe it exists. That's not a great way to reason about things. Well, to that I offer that writing incorrect assumptions and straw-man responses isn’t a great way to communicate. I actually see recursion every day, and I still stick by what I said. I even work on a team that builds recursive hardware that accelerates traversing recursive data structures. To me it really seems like you’re still not understanding my point about call stacks vs iteration. I’m sorry my posts are making you feel defensive. Maybe you missed the part where I mentioned that if you work in a language like Prolog that offers no choice, you don’t need to worry about it? The time to worry about it is when there’s a choice, like in C++ or JavaScript or Python. Keep using tail recursion, that’s a good way to avoid some of the problems with recursion!
  - YeGoblynQueenne 2y ago
    I'm not being defensive, but this conversation is getting nowhere and that's becoming a little frustrating. Maybe you don't see it but your comments in this thread are all along the lines of "don't use recursion"... until they're suddenly not. You wrote (https://news.ycombinator.com/item?id=42595354 https://news.ycombinator.com/item?id=42595354): >> Recursion is great for CS education, but recursion should be rarely/never used in production code. Tail call recursion is one exception to that - I see it in production code occasionally. But tail call recursion is limited to cases of 1-dimensional recursion that can be transformed into iteration - and iteration is better anyway, so even tail calls need some extra justification for use in production code. "... recursion should be rarely/never used in production code" and "even tail calls need some extra justification for use in production code". Then you listed the JPL coding guidelines that say "avoid recursion". And now you're saying that what you really meant was that yes, you should use recursion, and tail recursion, but that doesn't count because it can be replaced by iteration anyway? Then why not avoid the replacement service and have all your loops be iterative in the first place? Or is that your argument? I really can't tell. And I'm getting the feeling that you don't know exactly what you're arguing for yourself, especially if you say (big reveal) you are working with recursion everyday. What's this all about now? >> That’s not true, I think you’re misunderstanding the article you linked to. Primitive recursive functions require fixed bounds, but that is not the same thing as all iteration. The Church-Turing thesis proves that anything you call recursion can be iterated. Right, so now we're talking about unbounded iteration? Again that's not the impression I got from the discussion upthread. Is that the good, safe, NASA-compliant kind of coding practices you support? I don't think it is. >> Keep using tail recursion, that’s a good way to avoid some of the problems with recursion! Now you're just being patronising. I was hoping we could have a robust disagreement without taking the piss, but I guess this one too has gone the way of all the conversations on the internet. Let's end this hear then, I'll let you have the last word (since I wrote a bit already myself). And no hard feelings from me. Communication is difficult. Btw, this is interesting: >> I even work on a team that builds recursive hardware that accelerates traversing recursive data structures. If you want to say a couple of words about what that is, I'd be curious to hear.

by dahart 2y ago

YeGoblynQueenne 2y ago

>> There is no such thing as a “procedure that can’t run without recursion”, which I assumed you already knew, and you might want to keep in mind if you want to keep defending recursion. There is such a thing. Non-primitive recursive functions can't be converted to iteration. I'm sorry but where did I give examples that are "100% classroom problems"? I gave examples of production code that use Prolog, therefore recursion since Prolog has no iteration constructs: the three jobs in the industry I've held, and the airline software from Sicstus. I can also add IBM's Watson (it used Prolog), Datalog databases (recursion is the point), and the SWI-Prolog website which is running on an http server implemented in Prolog (they call that "eating their own dogfood"). Those are all things that people need in practice and not "classroom problems". There's plenty more Prolog code running in the wild but obviously I don't know every program anyone has ever written using Prolog. There's also code in Answer Set Programming (e.g. I'm aware of planners for robotics applications), Haskell (e.g. xmonad, a windows manager in Haskell) and plenty of code people write in Scheme, Scala, etc Lisps, that also don't have iteration constructs. There's plenty of recursion in "real world" and "production" situations. But I get the feeling you don't work with it, so you just don't believe it exists. That's not a great way to reason about things.

dahart 2y ago
> Non-primitive recursive functions can’t be converted to iteration. That’s not true, I think you’re misunderstanding the article you linked to. Primitive recursive functions require fixed bounds, but that is not the same thing as all iteration. The Church-Turing thesis proves that anything you call recursion can be iterated. > I'm sorry but where did I give examples that are "100% classroom problems"? I answered that question in the comment you replied to. > But I get the feeling you don't work with it, so you just don't believe it exists. That's not a great way to reason about things. Well, to that I offer that writing incorrect assumptions and straw-man responses isn’t a great way to communicate. I actually see recursion every day, and I still stick by what I said. I even work on a team that builds recursive hardware that accelerates traversing recursive data structures. To me it really seems like you’re still not understanding my point about call stacks vs iteration. I’m sorry my posts are making you feel defensive. Maybe you missed the part where I mentioned that if you work in a language like Prolog that offers no choice, you don’t need to worry about it? The time to worry about it is when there’s a choice, like in C++ or JavaScript or Python. Keep using tail recursion, that’s a good way to avoid some of the problems with recursion!
- YeGoblynQueenne 2y ago
  I'm not being defensive, but this conversation is getting nowhere and that's becoming a little frustrating. Maybe you don't see it but your comments in this thread are all along the lines of "don't use recursion"... until they're suddenly not. You wrote (https://news.ycombinator.com/item?id=42595354 https://news.ycombinator.com/item?id=42595354): >> Recursion is great for CS education, but recursion should be rarely/never used in production code. Tail call recursion is one exception to that - I see it in production code occasionally. But tail call recursion is limited to cases of 1-dimensional recursion that can be transformed into iteration - and iteration is better anyway, so even tail calls need some extra justification for use in production code. "... recursion should be rarely/never used in production code" and "even tail calls need some extra justification for use in production code". Then you listed the JPL coding guidelines that say "avoid recursion". And now you're saying that what you really meant was that yes, you should use recursion, and tail recursion, but that doesn't count because it can be replaced by iteration anyway? Then why not avoid the replacement service and have all your loops be iterative in the first place? Or is that your argument? I really can't tell. And I'm getting the feeling that you don't know exactly what you're arguing for yourself, especially if you say (big reveal) you are working with recursion everyday. What's this all about now? >> That’s not true, I think you’re misunderstanding the article you linked to. Primitive recursive functions require fixed bounds, but that is not the same thing as all iteration. The Church-Turing thesis proves that anything you call recursion can be iterated. Right, so now we're talking about unbounded iteration? Again that's not the impression I got from the discussion upthread. Is that the good, safe, NASA-compliant kind of coding practices you support? I don't think it is. >> Keep using tail recursion, that’s a good way to avoid some of the problems with recursion! Now you're just being patronising. I was hoping we could have a robust disagreement without taking the piss, but I guess this one too has gone the way of all the conversations on the internet. Let's end this hear then, I'll let you have the last word (since I wrote a bit already myself). And no hard feelings from me. Communication is difficult. Btw, this is interesting: >> I even work on a team that builds recursive hardware that accelerates traversing recursive data structures. If you want to say a couple of words about what that is, I'd be curious to hear.