How exactly does tail recursion work?
You ask why "it doesn't require stack to remember its return address".
I would like to turn this around. It does use the stack to remember the return address. The trick is that the function in which the tail recursion occurs has its own return address on the stack, and when it jumps to the called function, it will treat this as it's own return address.
Concretely, without tail call optimization:
f: ...
CALL g
RET
g:
...
RET
In this case, when g
is called, the stack will look like:
SP -> Return address of "g"
Return address of "f"
On the other hand, with tail call optimization:
f: ...
JUMP g
g:
...
RET
In this case, when g
is called, the stack will look like:
SP -> Return address of "f"
Clearly, when g
returns, it will return to the location where f
was called from.
EDIT: The example above use the case where one function calls another function. The mechanism is identical when the function calls itself.
The compiler is simply able to transform this
int fac_times (int n, int acc) {
if (n == 0) return acc;
else return fac_times(n - 1, acc * n);
}
into something like this:
int fac_times (int n, int acc) {
label:
if (n == 0) return acc;
acc *= n--;
goto label;
}