S
Stephen Horne
This is not tail recursion. There are tail recursive implementations
of factorial, but this is not one of them.
The following is IIRC the standard tail-recursive approach to the
factorial...
int factorial_internal (int p_So_Far, int n)
{
if (n == 0) return 1;
return factorial_internal (p_So_Far * n, n - 1);
}
int factorial (int n)
{
return factorial_internal (1, n);
}
It's a bit crappy to look at, but it isn't a real-world example of
where tail recursion is a good idea in my view - just a common
illustration of how a non-tail-recursive function can be translated
into a tail-recursive form by replacing working variables with
parameters. You can find this kind of thing in Haskell and ML
tutorials.
My personal view is that if you need to do this kind of thing, the
explicitly iterative form is a better choice than the tail recursive
form anyway.
BTW - I have given some thought to Pete Beckers assertion that C and
C++ compilers have been optimising recursion into iteration for some
time. It's actually quite a bit cleverer than it sounds on the
surface. A naive conversion - or rather a naive test for whether the
conversion is valid - could easily go badly wrong.
When working with tree data structures, a common approach I use is to
plan the modification before doing it, making node splitting and
rebalancing decisions and perhaps allocating memory for new nodes and
so on, but not modifying the existing nodes. This means I don't have
serious problems in cases where, e.g., it turns out I'm unable to
allocate enough memory for new nodes. I can still leave the tree in an
unmodified and therefore self-consistent state because I detect the
problem while planning. That said, the planning itself has to be
lightweight, at least when the data structure is in memory - yet the
plan has to be a variable size data structure since I cannot limit the
depth of the tree. Library code might be in use for a very long time.
My favorite approach is basically to build a plan as a linked list on
the stack, with each plan node being a local variable in one layer of
the recursion. When the plan is completed, it is either executed or
cleaned up by iterating through the list before the recursion unwinds.
This keeps the plan off the heap, and so long as the parameters to the
recursive call are handled carefully (generally limited to a single
pointer-to-plan-node) it's pretty efficient.
Trouble is, it will *look* tail recursive until you examine the
detail. The code *is* tail recursive, but there's a serious problem
with stack use. After all, each one of those plan nodes is just a
local variable at one layer of the recursion. They all have to be
separate. A naive conversion to an iterative implementation would mean
that all those plan nodes are found at the same location on the stack,
which is clearly invalid.
There's not necessarily any way for the compiler to know that that
looks-like-tail-recursion cannot be naively optimised. Data flow
analysis cannot do the job, in general, because the data flow can pass
through other nested function calls. For example...
void recursive (plan_node* p_prev)
{
if (planning_done (p_prev))
{
execute_plan (p_prev);
return;
}
plan_node l_next;
l_next.m_link = p_prev;
// other plan setup here
recursive (do_stuff (&l_next));
}
That is a pretty good representation of the structure of what I'd do
for a tree modification (particularly working leaf up, such as an
insert into a particular leaf node). The only oddity is the do_stuff
function - I can't think of a good reason for it in this case, but the
compiler cannot make assumptions about the limits of programmers
imaginations. It's there to make the point about data flow, though. In
this case, the compiler cannot know if the parameter to recursive will
be a pointer to l_next or not.
Of course this is just a variation on common dangling pointer issues
where there are pointers to local variables in functions that have
exited. The difference is that in this case, the function *hasn't*
exited, at least according to the promises made by the C and C++
languages.
Just about the only optimisation of recursion that can be done safely
in C++ is to spot a sequence in the generated assembler where a call
is followed pretty much immediately by a ret. This isn't a tail
recursion optimisation because it's much more general than even
recursion - many call-then-ret sequences can be optimised the same way
irrespective of whether they are recursive.
Even this needs some care WRT stack frame handling - you cannot assume
that the current functions locals will not be referenced somehow by
the called function, so in a sense you have to grow a larger stack
frame for the function with each level of recursion - only a part of
which is considered current, but the whole lot being popped when an
unoptimised ret is finally encountered.
That means that while stack growth may be reduced a little, it cannot
normally be completely avoided, and there is a cost even for the
reduction - a more complex stack-frame setup for the optimised
function call.
In other words, the promises made by claims of tail recursion
elimination are not met by this call optimisation approach.
This kind of thing is not an issue in Scheme since pretty much
everything is stored in dynamically allocated memory and garbage
collected, at least in principle. The tail recursion elimination is
guaranteed, whereas the stack storage optimisation is a matter for the
compiler to sort out, and Scheme compilers may fail to use stack
memory in cases where a C++ programmer would use a local variable.
Therefore, full tail recursion elimination of the kind done in Scheme
and other functional languages simply isn't viable in C or C++. The
nature of the languages means that the compiler can only determine
validity in certain special cases. Of course the qualification of
exactly what can and can't be handled probably isn't documented very
well for most compilers because the detail is probably rather complex,
because it probably changes between releases, and because the whole
point of automatic optimisation is to leave it to the optimiser and
not fuss about it.
Now, having made that assertion with absolute confidence, I'll sit
back and wait to be told just how wrong I am ;-)