4 ms·

> let me try arguing it this way: it is impossible for a non-tail-call-optimized recursion to use constant space. [...] What you're really saying here is that

> let me try arguing it this way: it is impossible for a non-tail-call-optimized recursion to use constant space. [...] What you're really saying here is that if you have a non-tail-call-optimizing compiler (i.e. if your compiler and/or language suck at optimizing recursion), and your algorithm uses enough stack space that the resulting cache pollution affects the performance (absolutely not every algorithm falls in this bucket!), then recursion is likely (not certain!) to be slower than recursion. I'm sure you know that even your first assumption immediately fails for all the (many) tools that handle tail-recursion just fine. Isn't it then a gross overgeneralization to just claim "iterative algorithms are faster than recursive ones", as if your situation is universally representative of everyone's? > i suppose one thing i should mention, i am thinking of extreme optimization use cases where the entire data structure fits in cache (or close to it). think like in-cache tries or similar. if you're hitting main memory with each iteration anyway, it doesn't really matter. FWIW, the scenario you're imagining is even more niche than that. You're assuming a case where, for example, the hardware prefetcher isn't able to predict (or doesn't have enough bandwidth to) fetch the next cache line before you need it. You're also assuming the data structure is large enough (or your access pattern unlucky enough) that cache misses are actually affecting you -- i.e. not just "fits in cache", but takes up most of the room, too. You're also assuming that compilers are equally good at optimizing recursion and iteration (aside from tail-recursion), which is also not true -- for example, large functions tend to get optimized more poorly than smaller ones (including more stack accesses!), and your iteration is much more likely result in large functions being generated. Are there situations in which your assumptions hold? Definitely. Are you way, way overgeneralizing? Sure looks like that too.

rstuart4133 2mo ago
I'm not the OP, but I think he's saying something much simpler than that. Typically with a recursive algorithm, the state you need to push is tiny. Usually a word or two. But often you need a lot of temporaries to calculate that state. If you use recursion, both the absolutely necessary state and the temporaries are pushed onto the stack (along with the stack frame the language runtime wants). If you use iteration, the programmer just pushes the necessary state onto the stack, and reuses the temporaries in place. The rest of his claims follow from those facts. Space consumption is less because you are saving less. Cache locality is better both because the temporaries aren't scattered across the stack, and because you are reusing the same locations over and over again. The downside of iterative solutions is stacks are more efficient memory allocators than heap algorithms - especially if you are forced to grow the array your pushing things onto many times. But if you know that in advance so you can allocate the full amount up front, then at the limit when N -> ∞ iteration will always win over recursion.
- a-dub 2mo ago
  that's basically the argument, thank you! the other person i was debating with was correct to push back on the scope of the generalization! but, in cases where the choice is actually meaningful towards a push to max performance, (not trivial loops as tail call optimizable recursions, further optimization), iteration is the way. recursions are easy to read, understand and reason about, but they also abstract away an implicit data structure choice where unrelated implementation details can impact overall performance.
  - dataflow 2mo ago
    Just replied to the parent, linking so you see it here: https://news.ycombinator.com/item?id=49165769 https://news.ycombinator.com/item?id=49165769
- dataflow 2mo ago
  Sorry for the late reply. > If you use recursion, both the absolutely necessary state and the temporaries are pushed onto the stack (along with the stack frame the language runtime wants). If you use iteration, the programmer just pushes the necessary state onto the stack, and reuses the temporaries in place. If that's the statement, what you (addressing both yourself & the OP) are arguing here is that it's easier to avoid unintentional temporaries with iteration. Nobody argued against that, it's obviously true. It clearly doesn't mean iteration is always faster, it just means achieving one particular outcome is easier with it. Before you drop your mic though: what you're missing here the ugly half of the picture, which is that this is because managing any state in the iterative version of arbitrary recursive calls is already a massive pain across calls [1], so of course you're unlikely to maintain unneeded state. Basically, when it comes to iteration, you're assuming arbitrary amounts of effort (I guess because it wouldn't run at all otherwise, let alone quickly), but when it comes to recursion, suddenly you're assuming low effort (I guess because low optimization effort still gets it running, just less quickly). That's... clearly an unfair comparison, and generalizing it to "iteration is faster than recursion" is silly. P.S.: I should perhaps point out that compilers can & do partially inline even unbounded recursion. For you to argue iteration is faster, you'd have to basically argue that compilers can (and do) make analogous optimizations for the equivalent iterative versions of the same algorithms (read: manual management of a stack buffer, etc.) across equivalent level traversals of the algorithm. Do you actually believe that to be true? I'm not gonna proclaim this is impossible or that compilers never do this, but I can say I sure as heck don't recall ever seeing or hearing of this. From what I've seen, iteration would generate shorter code, not necessarily faster code.

rstuart4133 2mo ago

I'm not the OP, but I think he's saying something much simpler than that. Typically with a recursive algorithm, the state you need to push is tiny. Usually a word or two. But often you need a lot of temporaries to calculate that state. If you use recursion, both the absolutely necessary state and the temporaries are pushed onto the stack (along with the stack frame the language runtime wants). If you use iteration, the programmer just pushes the necessary state onto the stack, and reuses the temporaries in place. The rest of his claims follow from those facts. Space consumption is less because you are saving less. Cache locality is better both because the temporaries aren't scattered across the stack, and because you are reusing the same locations over and over again. The downside of iterative solutions is stacks are more efficient memory allocators than heap algorithms - especially if you are forced to grow the array your pushing things onto many times. But if you know that in advance so you can allocate the full amount up front, then at the limit when N -> ∞ iteration will always win over recursion.

a-dub 2mo ago
that's basically the argument, thank you! the other person i was debating with was correct to push back on the scope of the generalization! but, in cases where the choice is actually meaningful towards a push to max performance, (not trivial loops as tail call optimizable recursions, further optimization), iteration is the way. recursions are easy to read, understand and reason about, but they also abstract away an implicit data structure choice where unrelated implementation details can impact overall performance.
- dataflow 2mo ago
  Just replied to the parent, linking so you see it here: https://news.ycombinator.com/item?id=49165769 https://news.ycombinator.com/item?id=49165769
dataflow 2mo ago
Sorry for the late reply. > If you use recursion, both the absolutely necessary state and the temporaries are pushed onto the stack (along with the stack frame the language runtime wants). If you use iteration, the programmer just pushes the necessary state onto the stack, and reuses the temporaries in place. If that's the statement, what you (addressing both yourself & the OP) are arguing here is that it's easier to avoid unintentional temporaries with iteration. Nobody argued against that, it's obviously true. It clearly doesn't mean iteration is always faster, it just means achieving one particular outcome is easier with it. Before you drop your mic though: what you're missing here the ugly half of the picture, which is that this is because managing any state in the iterative version of arbitrary recursive calls is already a massive pain across calls [1], so of course you're unlikely to maintain unneeded state. Basically, when it comes to iteration, you're assuming arbitrary amounts of effort (I guess because it wouldn't run at all otherwise, let alone quickly), but when it comes to recursion, suddenly you're assuming low effort (I guess because low optimization effort still gets it running, just less quickly). That's... clearly an unfair comparison, and generalizing it to "iteration is faster than recursion" is silly. P.S.: I should perhaps point out that compilers can & do partially inline even unbounded recursion. For you to argue iteration is faster, you'd have to basically argue that compilers can (and do) make analogous optimizations for the equivalent iterative versions of the same algorithms (read: manual management of a stack buffer, etc.) across equivalent level traversals of the algorithm. Do you actually believe that to be true? I'm not gonna proclaim this is impossible or that compilers never do this, but I can say I sure as heck don't recall ever seeing or hearing of this. From what I've seen, iteration would generate shorter code, not necessarily faster code.