4 ms·

> 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 recu

by 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.
- dahart 2y ago
  > Now you’re just being patronising. Jesus Christ, I was just trying to be nice. Your defensiveness is repeatedly leading to misunderstanding and getting in the way of us having a productive conversation. > Right, so now we’re talking about unbounded iteration? You’re conflating multiple different topics here. NASA doesn’t allow unbounded iteration. That’s a separate topic from whether recursion can theoretically be transformed into iteration. Recursion can always be transformed into iteration. That statement is not and never was dependent on what NASA does. There is no such thing as a recursive function that can’t be iterated. In practice, iterating is as efficient or more efficient than using a call stack. This is still and always was my point. If you’re using a call stack for recursion, you are wasting memory and cycles, which is one of the reasons “Software developed in Prolog has been criticised for having a high performance penalty compared to conventional programming languages.” https://en.wikipedia.org/wiki/Prolog#Limits https://en.wikipedia.org/wiki/Prolog#Limits I work on ray tracing hardware, which is conceptually recursive, uses recursive tree data structures, and often implemented using recursion. We make it faster by transforming the recursion into specialized iterative hardware, and also algorithms that do iteration in place of recursion. Computer graphics is full of algorithms that are conceptually recursive and yet always more efficient in practice if you avoid using call recursion and implement them iteratively instead. Character rig animation is one example. And browsers do this for rendering HTML.

by dahart 2y ago

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.

dahart 2y ago
> Now you’re just being patronising. Jesus Christ, I was just trying to be nice. Your defensiveness is repeatedly leading to misunderstanding and getting in the way of us having a productive conversation. > Right, so now we’re talking about unbounded iteration? You’re conflating multiple different topics here. NASA doesn’t allow unbounded iteration. That’s a separate topic from whether recursion can theoretically be transformed into iteration. Recursion can always be transformed into iteration. That statement is not and never was dependent on what NASA does. There is no such thing as a recursive function that can’t be iterated. In practice, iterating is as efficient or more efficient than using a call stack. This is still and always was my point. If you’re using a call stack for recursion, you are wasting memory and cycles, which is one of the reasons “Software developed in Prolog has been criticised for having a high performance penalty compared to conventional programming languages.” https://en.wikipedia.org/wiki/Prolog#Limits https://en.wikipedia.org/wiki/Prolog#Limits I work on ray tracing hardware, which is conceptually recursive, uses recursive tree data structures, and often implemented using recursion. We make it faster by transforming the recursion into specialized iterative hardware, and also algorithms that do iteration in place of recursion. Computer graphics is full of algorithms that are conceptually recursive and yet always more efficient in practice if you avoid using call recursion and implement them iteratively instead. Character rig animation is one example. And browsers do this for rendering HTML.