Danny Woods
11/3/2008 4:58:00 PM
Pete Becker <pete@versatilecoding.com> writes:
> On 2008-11-03 11:33:23 -0500, Danny Woods <dannywoodz@yahoo.co.uk> said:
>
>>
>> This is not tail recursion. Tail recursion is when the call to the
>> recursive function is the absolute LAST thing to happen in the function
>> body.
>
> That is one possible definition of tail recursion, and not a
> particularly useful one. Please give an example of a function that's
> tail recursive under this definition and does something useful.
Sorry, but I have to disagree here: it's not a possible definition, it's
pretty much *the* definition :-). A function cannot be considered tail
recursive if it has work do do after the call to itself. The example is
pretty much the helper function that you don't seem to like (and, if I'm
being honest, quite rightly so: tail recursion tends to fit more neatly
with functional(-ish) languages like Lisp and Erlang than C++).
>
>> This lack of additional computation allows the new recursive call
>> to take place of the original on the stack, if such an optimisation is
>> available for your compiler.
>>
>> In the example give, the return value of the recursive call is added to
>> 1/n, so there's at least an addition happening once the function
>> returns.
>
> Which in no way prevents turning the recursion into a loop.
Agreed. No issue with converting it into a loop. Just whether or not
it's one that involves layering the stack when the code could be written
to avoid it.
>
>>
>> The normal practice to make a function tail recursive is to create a
>> helper function that takes an accumulator value, something like this:
>>
>> int harmonic_helper(int n, int acc)
>> {
>> if (n == 1) return acc + 1;
>> else return harmonic_helper(n - 1, acc + (1 / n));
>> }
>
> Oh, I see what you're saying. That's far more complex than it needs to
> be. Any self-respecting compiler can optimize the original form of the
> code.
Whether or not it's complex depends upon how often you see that kind of
construct :-) In the Lisp world, it's pretty standard practice, although
its normally possible to embed the helper function in the caller with
the 'labels' macro to avoid cluttering up the source file with helper
functions.
With regard to the C++ implementation, I'm not a compiler wizard, so
I'll defer.
Cheers,
Danny.