4 ms·
It doesn't make any sense to convert any arbitrary recursion into tail called optimized. If the recursion can be tail called optimized then yes the loop is the
by Herval_freire 4y ago
It doesn't make any sense to convert any arbitrary recursion into tail called optimized.
If the recursion can be tail called optimized then yes the loop is the optimized performant implementation.
But if the recursion fundamentally utilizes the call stack then the reverse is actually true. The recursion is now the performant implementation of a for loop. So a loop conversion optimization actually doesn't make sense here. That's partly why a compiler won't optimize this.
Why? Because in recursion you utilize the call stack, in the for loop you're going to create a heap allocated stack and allocate on it repeatedly. Allocation slows down the iterations.
The only advantage of the for loop in this case is that there won't be stack overflow, but overall the recursive version will actually be faster.
- mike_hock 4y agoWorks for O(log n) stack depth. In general, recursion is not viable.
- zelphirkalt 4y agoThis is quite false. Languages like Scheme (dialects), ML variants, Erlang and Haskell all make use of recursion in general and they produce very viable results.
- sokoloff 4y ago> If the recursion can be tail called optimized then yes the loop is the optimized performant implementation. Is it? My mental model of tail-call optimization is that it’s just a replacement of the stack variable values in place and a jump to the function entry point (which seems like the same amount of work as updating local variables in a loop and jumping to the head of the loop).
- deleted 4y ago[deleted]
- zelphirkalt 4y ago> The only advantage of the for loop in this case is that there won't be stack overflow, but overall the recursive version will actually be faster. In languages, which have realized the value of recursion, a stack overflow does not happen. For example: https://docs.racket-lang.org/guide/Lists__Iteration__and_Recursion.html https://docs.racket-lang.org/guide/Lists__Iteration__and_Rec...
- soegaard 4y agohttps://stackoverflow.com/questions/49912204/why-there-is-no-such-thing-as-stack-overflow-in-racket https://stackoverflow.com/questions/49912204/why-there-is-no...