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.

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.

Works for O(log n) stack depth. In general, recursion is not viable.

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.

> 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).

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

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

> all recursion that explicitly returns a function call

Yeah, but that's not "all recursion".

> 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

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.