Why is tail recursion better than regular recursion?

There is the axiom you should always prefer tail-recursion over regular recursion whenever possible. (I'm not considering tabulation as an alternative in this question).

I understand the idea by why is that the case? Is it only because of the compiler can optimize the recursive call in case of tail recursion? if that is the only reason, why the compiler would not be able to optimize the regular recursive call?

if that is the only reason, why the compiler would not be able to optimize the regular recursive call?

You are focusing on the wrong thing here: the reason the optimization works is because of the tail part, not because of the recursion part.

Tail-recursion elimination is a special case of tail-call elimination, not a special case of some form of recursion optimization.

Normally, when you call a subroutine, you have to "remember" where you called from and what the current state is, so that you can continue the execution when you come back from the return.

So, for example, if you have something like:
function foo() {
bar();
baz();
qux();
}


Then before the call to bar() and before the call to baz(), you have to store the current state and restore it after bar() returns and after baz() returns. But, since the call to qux() is a tail-call, you know that there is nothing that will be executed after you return back, so you can skip the whole "remember and restore" bit. Instead, you can simply jump to qux. It is literally equivalent to a GOTO.

Tail-recursion is the intersection of a tail-call and a recursive call: it is a recursive call that also is in tail position, or a tail-call that also is a recursive call. This means that a tail-recursive call can be optimized the same way as a tail-call.

Now, an obvious question is: if a tail-recursive call can be optimized the same way as a tail-call, why do we care specifically about tail-recursive calls and not just about tail-calls in general?

Well, first of all: we do care about tail-calls in general. Tail-calls allow writing some code in a very elegant manner that is hard to express otherwise. For example, if you have tail-calls, then you can simply express a state machine using subroutine calls: every state is a subroutine and every transition is a call – this makes the code look like a direct translation of how you would draw the state machine on paper, and the control flow graph of the code matches exactly the state machine. Since these calls never return, you would quickly run out of stack space if tail-calls weren't optimized. Without tail-calls, state machines are typically implemented as state tables, with GOTOs, and that code does not look at all like the drawing of a state machine.

The reason why we care about tail-recursion as distinct from general tail-calls, and specifically why we care about direct tail-recursion, i.e. where a subroutine directly tail-calls itself (foo calls foo) instead of indirectly via another subroutine (foo calls bar, bar calls foo) is because some widely-used platforms do not support generalized non-local control constructs such as GOTO, which are needed to efficiently implement tail-calls. In other words: optimizing tail-recursion is the same as a loop (which most target languages support), optimizing tail-calls is the same as an unrestricted GOTO (which many target platforms, e.g. JVM, ECMAScript, CLI) do not support.

For example, on the JVM, it is possible to implement tail-calls, but it is complex and slow and hinders interoperability with other JVM languages, because the JVM does not have unrestricted GOTO or the ability to reflectively manipulate the stack or Continuations or something similar.

The JVM does, however, have a GOTO that allows to jump to a different location within the same method. Java uses this to implement loops for example, but it can also be used to implement direct tail-recursion. So, the reason why we care about direct tail-recursion specially, is because there are widely-used platforms where implementing direct tail-recursion is easy but implementing general tail-calls is infeasible (meaning, it is technically possible but it wouldn't make sense because it negates the reasons why you chose that platform in the first place – e.g. on the JVM, it makes your language slow or badly interoperable with other JVM languages, but the performance of the JVM and the ability to interoperate with other languages are precisely the reasons why you chose the JVM as a platform in the first place).

An important sidenote: in your question, you used the term "optimization", as did I in my answer. However, it is important to distinguish between an optimization and a language feature. An optimization is a private internal implementation detail of a particular version of a particular implementation of the language. It is entirely optional. For example, compiler A may perform a particular optimization but compiler B may not. A real-world instance of this is that the Oracle HotSpot JVM performs Escape Analysis but no Escape Detection whereas the Azul Zing JVM does perform both EA and ED. And neither the Oracle HotSpot JVM nor Azul Zing JVM perform tail-call optimization but the Eclipse OpenJ9 JVM (formerly IBM J9) does eliminate some tail-calls under some conditions.

So, an optimization may or may not be implemented at all by a particular implementation, and it may

StackExchange Computer Science Q#148055, answer score: 48