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 or may not be performed in a particular situation.
A language feature, however, must be implemented by all conforming implementations. Tail-Call optimization (TCO) is, as the name implies, an optimization. It is not mandatory. The corresponding language feature is typically called Proper Tail-Calls or Properly Implemented Tail-Call Handling (PITCH). A language with Proper Tail-Calls or PITCH basically has a section in its language specification that says "all implementations must perform TCO under these conditions", and so in some sense, PITCH is simply just "language-mandated TCO", but it is important to distinguish between an optional optimization that may or may not exist in a particular implementation and may or may not be performed in a particular situation, and a mandatory feature that must be implemented by all implementations and must be performed under all circumstances prescribed in the specification.
For example, many C and C++ compilers will perform TCO under some limited set of circumstances, but there is no guarantee if or when they will do it. So, you cannot write code that relies on it (like the state machine example above) because you cannot know when you write the code whether the optimization will actually happen or not.
The same thing applies to Tail-Recursion Elimination (TRE). TRE is an optimization that is not guaranteed to happen. As far as I know, there is no common name for the language feature that corresponds to the optimization (like there is with PITCH / Proper Tail-Calls for TCO). It is typically just called Tail-Recursion, although I call it Proper Tail-Recursion in analogy to the Proper Tail-Calls.
The way a standard function/procedure (from now on I'll just say "function") call works is that the caller needs to store onto the stack whatever state it needs for computations that occur after the call, and then the call occurs. Calling a function may also require manipulating the stack; on many current CPUs, issuing a call involves pushing the return address onto the stack. When the call returns, the state is retrieved from the stack, then any following computations are performed.
If the call is a tail call (i.e. it is the last thing to happen in the caller), however, then by definition no computation follows. So if everything is right and the stars align, the tail call can be implemented as a jump instruction. And in the case where the tail call is to the function itself (i.e. tail recursion), this can be implemented as a loop.
Programming language semantics do not always allow this optimisation; in C++, for example, destructors or code to manipulate the exception state may need to run after a tail call. However, it is needed in programming languages without a loop statement, because that is the only way to implement a loop using constant stack space. It is so important that in some languages, most notably Scheme, tail call optimisation is written into the language definition.
There are other options. The Mercury programming language implements something called "middle recursion", which you can read all about here:
(Full disclosure: I'm one of the original Mercury developers.)
It's also not unheard of for compilers to give a function more than one entry point, one for "real" calls and one for "tail" calls, if that is more convenient for the ABI (e.g. to handle callee-save registers correctly).
tail recustion is better becaus a good compiler can optimise it into a goto, thus it doesn't consume any stack space fro the recusrion or waste time returning.
foo(a){
m=bar(a);
if(z) return foo(a-1);
return m;
}
becomes
foo(a){
refoo:
m=bar(a);
if(z){
a=a-1;
goto re_foo;
}
return m;
}
goto, since because there might be other variables aside from a involved whose values you have to consider. The benefit is that you don't need to retain the stack frame of the caller, allowing you to reuse the space for the stack frame of the recursive call.
$\endgroup$
Tail-recursive calls are better than other recursive calls because you can optimize away the return. Let’s say you try to write
fibonacci n =
fibonacci (n-1) +
fibonacci (n-2)
Can either call be optimized? No, because it'll turn into something like
push n on the stack
push the argument n-1
call fibonacci and save the return value
retrieve n from the stack and push n-2
call fibonacci and save the return value
add the two return values
return
You can’t just transfer control to either function you’re calling, because there’s always something to be done afterwards, and you can’t re-use the same stack frame for the call, because you have something saved on the stack that you will need after it returns.
Tail-recursive calls are also better than most tail calls (although not all other tail calls) because you’re calling the same function. So, you will always be passing the same number of arguments in the same format. You also won’t be returning, so you can throw away anything else on the stack or registers and re-use the exact same stack frame. Often, you’ll be passing the tail-recursive call some of the same parameters unchanged, and the function body doesn’t have to insert any code to pass them.
In fact, making a tail-recursive call optimizes to exactly the same code as optimizing and jumping back to the start of the code block. Which is exactly the same code as a loop. If you check out the assembly that a while loop and its equivalent as a tail-recursive function compile to, you will see that this is nearly identical. Decades ago, computer scientists often believed that they should start out by writing a recursive algorithm, since those are easier to understand and prove correct, then turn it into a tight loop, because those were faster. But now, if you write it tail-recursively, the compiler does that transformation for you, and you get the best of both.
Tail-recursion also lets you use functional programming. Loop variables have to be mutable, so it’s hard for the compiler to check that they haven’t been updated too often, or not updated when they should have been. Not only for humans. It’s also harder for the compiler to figure out what optimizations are safe to make.
With tail recursion, if you make your function’s input immutable, the state is only updated once per recursion, when you make a call, and all local state is updated once and only once, all together. There is no other local state that can creep in. It’s easy to reason about, prove correct, and optimize.
