4 ms·

>Nobody has yet convinced me that recursion has any sustained advantage over looping. Recursion gives you a stack by default. You don't have to explicitly thin

>Nobody has yet convinced me that recursion has any sustained advantage over looping. Recursion gives you a stack by default. You don't have to explicitly think about the stack. In looping the stack must be explicit. Recursion and looping are the same thing. Recursion can be mechanically translated to a for loop and a stack, the concepts are isomorphic.

KRAKRISMOTT 4y ago
On paper perhaps, but I have yet to see a compiler that can take any arbitrary recursive subroutine and automatically optimize it into a Tail Call Optimized (that is, transform the recursive parts into goto/jumps similar to a loop) version. Non optimized recursion is not hard to understand, the problem is any performant recursive code needs to be manually rewritten as tail recursive which adds a lot of complexity. Built a better compiler and maybe more people would be willing to embrace functional programming.
- illiarian 4y ago
  Unless I'm mistaken, Erlang's compiler rewrites all recursion that explicitly returns a function call into tail-call, and eliminates all the stack in between
  - timmg 4y ago
    > all recursion that explicitly returns a function call Yeah, but that's not "all recursion".
- 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 ago
    Works for O(log n) stack depth. In general, recursion is not viable.
    - zelphirkalt 4y ago
      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.
  - 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 ago
      https://stackoverflow.com/questions/49912204/why-there-is-no-such-thing-as-stack-overflow-in-racket https://stackoverflow.com/questions/49912204/why-there-is-no...
- chriswarbo 4y ago
  > On paper perhaps, but I have yet to see a compiler that can take any arbitrary recursive subroutine and automatically optimize it into a Tail Call Optimized (that is, transform the recursive parts into goto/jumps similar to a loop) version. General recursion can be modelled coinductively via the "Delay" or "Partial" type, e.g. https://arxiv.org/abs/cs/0505037 https://arxiv.org/abs/cs/0505037 Type-inference can figure out when recursive calls need to be wrapped in `Later`. We can then compile into a single `while` loop to unwrap the layers.

KRAKRISMOTT 4y ago

On paper perhaps, but I have yet to see a compiler that can take any arbitrary recursive subroutine and automatically optimize it into a Tail Call Optimized (that is, transform the recursive parts into goto/jumps similar to a loop) version. Non optimized recursion is not hard to understand, the problem is any performant recursive code needs to be manually rewritten as tail recursive which adds a lot of complexity. Built a better compiler and maybe more people would be willing to embrace functional programming.

illiarian 4y ago
Unless I'm mistaken, Erlang's compiler rewrites all recursion that explicitly returns a function call into tail-call, and eliminates all the stack in between
- timmg 4y ago
  > all recursion that explicitly returns a function call Yeah, but that's not "all recursion".
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 ago
  Works for O(log n) stack depth. In general, recursion is not viable.
  - zelphirkalt 4y ago
    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.
- 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 ago
    https://stackoverflow.com/questions/49912204/why-there-is-no-such-thing-as-stack-overflow-in-racket https://stackoverflow.com/questions/49912204/why-there-is-no...
chriswarbo 4y ago
> On paper perhaps, but I have yet to see a compiler that can take any arbitrary recursive subroutine and automatically optimize it into a Tail Call Optimized (that is, transform the recursive parts into goto/jumps similar to a loop) version. General recursion can be modelled coinductively via the "Delay" or "Partial" type, e.g. https://arxiv.org/abs/cs/0505037 https://arxiv.org/abs/cs/0505037 Type-inference can figure out when recursive calls need to be wrapped in `Later`. We can then compile into a single `while` loop to unwrap the layers.