News for hackers. Stuff that matters.
Re:Mindset Shifts for Functional Programming by Herval_freire on Wednesday April 05, 2023 @11:27AM (#35455811)
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.

I think the overflow may be part of the reason why the reverse conversion isn't done of taking heap allocated stacks and converting them into call stacks. The other issue is ownership of the heap allocated stacks, you can't convert it to a call stack if other entities own it or something else references it.

Re:Mindset Shifts for Functional Programming by mike_hock on Wednesday April 05, 2023 @01:48PM (#35457896)
Works for O(log n) stack depth. In general, recursion is not viable.
Re:Mindset Shifts for Functional Programming by zelphirkalt on Wednesday April 05, 2023 @02:40PM (#35458653)
This 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.
Re:Mindset Shifts for Functional Programming by sokoloff on Wednesday April 05, 2023 @02:28PM (#35458483)
> 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).

Re:Mindset Shifts for Functional Programming by zelphirkalt on Wednesday April 05, 2023 @02:38PM (#35458625)
> 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_Rec...

Re:Mindset Shifts for Functional Programming by soegaard on Thursday April 06, 2023 @01:39PM (#35471736)