Re: Tail Recursion, Stack and Function Call after "return"

"sawer" wrote:
"A recursive call is tail recursive when it is the last
statement that will
be executed within the body of a function and its return value
is not a part
of an expression"

In addition to Igor's answer. Tail Recursion Optimization
(actually it's a private case of Tail Call Optimization, TCO)
won't kick in if there are local objects that have non-trivial
destructors. It is because these destructors must run before
caller function returns. So there is more code to run beyond
`return' statement:

int foo()
{
X x; // has destructor

return bar();
} // ~X::X runs here after `return' statement

In pseudocode it may look like this:

int foo()
{
X x; // has destructor

int __tmp = bar(); // it isn't "tail" anymore

~X::X(&x);

return __tmp;
}

Also, of there is a reference of local variables of the caller in
callee arguments, then TCO likely to lead to undefined results,
hence it will be discarded. Consider following code:

int bar(int* arg);

int foo()
{
int a = 42;

return bar(&a);
}

In the above code TCO can't be performed, since `a' variable must
be valid and occupy a storage on stack during execution of `bar'.
It means that foo's stack frame cannot be eliminated until the end
of `bar' call, therefore TCO will be cancelled.

HTH
Alex


.

Relevant Pages
Quantcast