is it tail recursion

[Andrey Tarasevich]

Re: is it tail recursion

Stephen Horne wrote:

>
If that initial example is being optimised using "tail recursion
elimination", there's a terminology confusion issue. If you claim that
Muzammils example is tail recursive, you may as well claim that all
recursion is tail recursion - it's possible to convert *any* recursive
algorithm into an iterative algorithm, but that has nothing to do with
tail recursion.

Firstly, that latter statement is incorrect or, more precisely, based on
a popular terminological mix-up. In general case it is not possible to
convert any recursive algorithm into an iterative one. What's really
possible is to provide an iterative _implementation _ for a recursive
algorithm, i.e. implement it without using the language-level syntactic
recursion. In other words, it is always possible to implement recursion
"manually", instead of using the language-provided (syntactic)
mechanisms. We all know how to do that, but while the resultant
implementation is formally iterative, the algorithm it implements still
remains recursive in general case. In languages that provide no support
for syntactic recursion, the only option is to simulate it by using a
"manual" implementation. Following this approach it is perfectly
possible to implement recursive algorithms in such languages, which
illustrates the difference between the algorithm and its implementation.
Understanding it is crucial for a meaningless discussion on the subject.

Secondly, when a given recursive algorithm allows for a formally
iterative implementation with _constant_ _memory_ requirement (meaning
that the recursion depth has to be limited by a constant), this
immediately indicates that there was no real need for the recursion in
the original algorithm in the first place, and that it can be
re-formulated as an iterative algorithm (with a straightforward
iterative implementation) . The whole point of separating certain
algorithms into a class of so called tail-recursive algorithms is to
indicate the they possess the property of being convertible into a truly
iterative form in the most obvious way.

--
Best regards,
Andrey Tarasevich

[Muzammil]

Re: is it tail recursion

On Nov 4, 6:33 am, Andrey Tarasevich <andreytarasev. ..@hotmail.com>
wrote:

Stephen Horne wrote:
>

If that initial example is being optimised using "tail recursion
elimination", there's a terminology confusion issue. If you claim that
Muzammils example is tail recursive, you may as well claim that all
recursion is tail recursion - it's possible to convert *any* recursive
algorithm into an iterative algorithm, but that has nothing to do with
tail recursion.

>
Firstly, that latter statement is incorrect or, more precisely, based on
a popular terminological mix-up. In general case it is not possible to
convert any recursive algorithm into an iterative one. What's really
possible is to provide an iterative _implementation _ for a recursive
algorithm, i.e. implement it without using the language-level syntactic
recursion. In other words, it is always possible to implement recursion
"manually", instead of using the language-provided (syntactic)
mechanisms. We all know how to do that, but while the resultant
implementation is formally iterative, the algorithm it implements still
remains recursive in general case. In languages that provide no support
for syntactic recursion, the only option is to simulate it by using a
"manual" implementation. Following this approach it is perfectly
possible to implement recursive algorithms in such languages, which
illustrates the difference between the algorithm and its implementation.
Understanding it is crucial for a meaningless discussion on the subject.
>
Secondly, when a given recursive algorithm allows for a formally
iterative implementation with _constant_ _memory_ requirement (meaning
that the recursion depth has to be limited by a constant), this
immediately indicates that there was no real need for the recursion in
the original algorithm in the first place, and that it can be
re-formulated as an iterative algorithm (with a straightforward
iterative implementation) . The whole point of separating certain
algorithms into a class of so called tail-recursive algorithms is to
indicate the they possess the property of being convertible into a truly
iterative form in the most obvious way.
>
--
Best regards,
Andrey Tarasevich

ok explain me this one .
int factorial (int n)
{
if (n==0) return 1;
else
factorail(n-1)*n;
}

why this recursion is tail recursion and harmonic is not.
i got your points.
but me is confusing about this factorial function.
why factorial function is tail recursion.????? ??????why

[Danny Woods]

Re: is it tail recursion

Muzammil <muzammilPeer98 7@gmail.comwrit es:

ok explain me this one .
int factorial (int n)
{
if (n==0) return 1;
else
factorail(n-1)*n;
}
>
why this recursion is tail recursion and harmonic is not.
i got your points.

This is not tail recursion :-)

Tail recursion can be identified quite easily by asking yourself this
question:

'Does anything happen in the function body AFTER the recursive call to
the function?'

If the answer is no, it's not tail recursive.

In the example you've given, the return value of the function is
multiplied by n, so the last thing happening in that function is a
multiplication. The SECOND last thing is the recursive function call,
but that's not enough to qualify for tail recursion. Also, there is no
generalised mapping between recursion and tail recursion, so a compiler
would have a hard time turning this code into a tail-optimized version
(there is, however, a generalised mapping between tail-recursion and
iteration, which is why it's appealing to functional programmers when
optimising code to spend the effort turning their recursive functions
into tail recursive equivalents).

Again, the standard way to acheive this would be with a helper function
that takes the current value of 'n' and an accumulator value:

int factorial_helpe r(int n, int a)
{
if (n == 0) return a;
else return factorial_helpe r(n - 1, n * a);
}

int factorial(int n)
{
return factorial_helpe r(n, 1);
}

Here, the required calculations occur BEFORE the function call, which is
the LAST thing in the function, making this eligible for tail call
elimination.

Hope this helps.

Cheers,
Danny.

[James Kanze]

Re: is it tail recursion

On Nov 4, 5:52 am, Muzammil <muzammilPeer.. .@gmail.comwrot e:

On Nov 4, 6:33 am, Andrey Tarasevich
<andreytarasev. ..@hotmail.comw rote:

Stephen Horne wrote:

[...]

Secondly, when a given recursive algorithm allows for a
formally iterative implementation with _constant_ _memory_
requirement (meaning that the recursion depth has to be
limited by a constant), this immediately indicates that
there was no real need for the recursion in the original
algorithm in the first place, and that it can be
re-formulated as an iterative algorithm (with a
straightforward iterative implementation) . The whole point
of separating certain algorithms into a class of so called
tail-recursive algorithms is to indicate the they possess
the property of being convertible into a truly iterative
form in the most obvious way.

ok explain me this one .
int factorial (int n)
{
if (n==0) return 1;
else
factorail(n-1)*n;
}

Why this recursion is tail recursion and harmonic is not?

Is it tail recursive? If it is, the harmonic also is; if the
harmonic isn't, then it isn't. It's really a question of
definition. The classical academic definition (at least
according to a quick search on the net---so absolutely no
guarantees) of tail recursion seems to be: "A recursive function
is said to be tail recursive if there are no pending operations
to be performed on return from a recursive call.", and another
site says that "The basic idea behind tail Recursion is to
eliminate the storage of any state information across the
recursive steps." According to these, factorial isn't tail
recursive, because there's a multiplication operation in
suspence when the funtion calls itself, and state information
(the n which will be multiplied) is required accross the
recursive call. As Pete has pointed out informally, and Andrey
more formally, this is one of those academic definitions which
are totally useless in practice, because they don't add anything
to the understanding, nor to what we can do. In practice, the
important point is the one Andrey made: that the total state
that must be saved must be constant, independant of number of
recursions. In such cases, any compiler which does "tail
recursion optimization" will be able to apply it, regardless of
whether the pedants decide to call it tail recursion or not.

Note that the presense of destructors in C++ may render
problematic detection of when this optimization can be applied,
so it's best not to count on it. Given that C++ does provide
many clean (and some not so clean) ways of writing iteration,
I'd suggest using those instead.

--
James Kanze (GABI Software) email:james.kan ze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

[Danny Woods]

Re: is it tail recursion

Danny Woods <dannywoodz@yah oo.co.ukwrites:

Tail recursion can be identified quite easily by asking yourself this
question:
>
'Does anything happen in the function body AFTER the recursive call to
the function?'
>
If the answer is no, it's not tail recursive.

Shouldn't post before the morning cup of tea...

If the answer is 'no', it IS tail recursive.

If there are any further operations going one once the recursive call
returns, it is NOT tail recursive.

Danny.

[courpron@gmail.com]

Re: is it tail recursion

On 4 nov, 10:25, James Kanze <james.ka...@gm ail.comwrote:

On Nov 4, 5:52 am, Muzammil <muzammilPeer.. .@gmail.comwrot e:
>
>

Secondly, when a given recursive algorithm allows for a
formally iterative implementation with _constant_ _memory_
requirement (meaning that the recursion depth has to be
limited by a constant), this immediately indicates that
there was no real need for the recursion in the original
algorithm in the first place, and that it can be
re-formulated as an iterative algorithm (with a
straightforward iterative implementation) . The whole point
of separating certain algorithms into a class of so called
tail-recursive algorithms is to indicate the they possess
the property of being convertible into a truly iterative
form in the most obvious way.

ok explain me this one .
int factorial (int n)
{
if (n==0)  return 1;
else
factorail(n-1)*n;
}
Why this recursion is tail recursion and harmonic is not?

>
Is it tail recursive?  If it is, the harmonic also is; if the
harmonic isn't, then it isn't.  It's really a question of
definition.  The classical academic definition (at least
according to a quick search on the net---so absolutely no
guarantees) of tail recursion seems to be: "A recursive function
is said to be tail recursive if there are no pending operations
to be performed on return from a recursive call.", and another
site says that "The basic idea behind tail Recursion is to
eliminate the storage of any state information across the
recursive steps."  According to these, factorial isn't tail
recursive, because there's a multiplication operation in
suspence when the funtion calls itself, and state information
(the n which will be multiplied) is required accross the
recursive call.  As Pete has pointed out informally, and Andrey
more formally, this is one of those academic definitions which
are totally useless in practice, because they don't add anything
to the understanding, nor to what we can do.  In practice, the
important point is the one Andrey made: that the total state
that must be saved must be constant, independant of number of
recursions.  In such cases, any compiler which does "tail
recursion optimization" will be able to apply it, regardless of
whether the pedants decide to call it tail recursion or not.

The strict tail recursion definition is not useless at all. It is used
by many functional programmers. This is an important concept to avoid
stack overflow / boost performances as most compilers will implement
TCE, and I mean true TCE, there are optimizations that transform non-
tail recursions to tail ones before applying TCE, but less compilers
do it. That's why functional programmers use techniques like the one
given by Danny Woods.

Since we are on a C++ newsgroup, let's talk about C++ compilers and
their behavior when confronted with the factorial recursive function :

int fac (int n)
{
if (n==0)
return 1;
else
return fac(n-1) * n;
}

VC++9 won't apply TCE while GCCv4 will.

But if, as a functional programmer, we use an accumlulator to obtain
TRUE tail recursion (from the academic definition) :

int fac (int n, int acc)
{
if (n==0)
return acc;
else
return fac(n-1, acc*n );
}

then both VC++ and GCC will apply TCE.

And in functional languages, the situation is more chaotic. The only
sure way to get TCE is to implement *true* tail recursion.

Alexandre Courpron.

[Dilip]

Re: is it tail recursion

On Nov 4, 3:25 am, James Kanze <james.ka...@gm ail.comwrote:

On Nov 4, 5:52 am, Muzammil <muzammilPeer.. .@gmail.comwrot e:
>

On Nov 4, 6:33 am, Andrey Tarasevich
<andreytarasev. ..@hotmail.comw rote:

Stephen Horne wrote:

>
    [...]
>
>
>

Secondly, when a given recursive algorithm allows for a
formally iterative implementation with _constant_ _memory_
requirement (meaning that the recursion depth has to be
limited by a constant), this immediately indicates that
there was no real need for the recursion in the original
algorithm in the first place, and that it can be
re-formulated as an iterative algorithm (with a
straightforward iterative implementation) . The whole point
of separating certain algorithms into a class of so called
tail-recursive algorithms is to indicate the they possess
the property of being convertible into a truly iterative
form in the most obvious way.

ok explain me this one .
int factorial (int n)
{
if (n==0)  return 1;
else
factorail(n-1)*n;
}
Why this recursion is tail recursion and harmonic is not?

>
Is it tail recursive?  If it is, the harmonic also is; if the
harmonic isn't, then it isn't.  It's really a question of
definition.  The classical academic definition (at least
according to a quick search on the net---so absolutely no
guarantees) of tail recursion seems to be: "A recursive function
is said to be tail recursive if there are no pending operations
to be performed on return from a recursive call.", and another
site says that "The basic idea behind tail Recursion is to
eliminate the storage of any state information across the
recursive steps."  

James
In the past I have found this[1] post to be very informative in
understanding tail recursion. The example is in the functional
language is F# running on Common Language Runtime (CLR) but the
concepts should stand irrespective of that. BTW, that post seems to
agree with your first definition of tail recursion.

[1] http://blogs.msdn.com/chrsmith/archi...recursion.aspx

[Pete Becker]

Re: is it tail recursion

On 2008-11-04 10:04:36 -0500, courpron@gmail. com said:

>
Since we are on a C++ newsgroup, let's talk about C++ compilers and
their behavior when confronted with the factorial recursive function :
>
int fac (int n)
{
if (n==0)
return 1;
else
return fac(n-1) * n;
}
>
VC++9 won't apply TCE while GCCv4 will.

What happens if you write the return statement as:

return n * fac(n-1);

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

[courpron@gmail.com]

Re: is it tail recursion

On 4 nov, 17:28, Pete Becker <p...@versatile coding.comwrote :

On 2008-11-04 10:04:36 -0500, courp...@gmail. com said:
>
>
>

Since we are on a C++ newsgroup, let's talk about C++ compilers and
their behavior when confronted with the factorial recursive function :

>

int fac (int n)
{
    if (n==0)
        return 1;
    else
        return fac(n-1) * n;
}

>

VC++9 won't apply TCE while GCCv4 will.

>
What happens if you write the return statement as:
>
        return n * fac(n-1);
>

Same thing ( it won't trigger TCE for VC++9 ).


Alexandre Courpron.

[Pete Becker]

Re: is it tail recursion

On 2008-11-04 11:58:49 -0500, courpron@gmail. com said:

On 4 nov, 17:28, Pete Becker <p...@versatile coding.comwrote :

>On 2008-11-04 10:04:36 -0500, courp...@gmail. com said:
>>
>>
>>

>>Since we are on a C++ newsgroup, let's talk about C++ compilers and
>>their behavior when confronted with the factorial recursive function :

>>

>>int fac (int n)
>>{
>>    if (n==0)
>>        return 1;
>>    else
>>        return fac(n-1) * n;
>>}

>>

>>VC++9 won't apply TCE while GCCv4 will.

>>
>What happens if you write the return statement as:
>>
>        return n * fac(n-1);
>>

>
Same thing ( it won't trigger TCE for VC++9 ).
>

Thanks.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

[James Kanze]

Re: is it tail recursion

On Nov 4, 4:04 pm, courp...@gmail. com wrote:

On 4 nov, 10:25, James Kanze <james.ka...@gm ail.comwrote:

On Nov 4, 5:52 am, Muzammil <muzammilPeer.. .@gmail.comwrot e:

Secondly, when a given recursive algorithm allows for a
formally iterative implementation with _constant_
_memory_ requirement (meaning that the recursion depth
has to be limited by a constant), this immediately
indicates that there was no real need for the recursion
in the original algorithm in the first place, and that
it can be re-formulated as an iterative algorithm (with
a straightforward iterative implementation) . The whole
point of separating certain algorithms into a class of
so called tail-recursive algorithms is to indicate the
they possess the property of being convertible into a
truly iterative form in the most obvious way.
ok explain me this one .
int factorial (int n)
{
if (n==0) return 1;
else
factorail(n-1)*n;
}
Why this recursion is tail recursion and harmonic is not?

Is it tail recursive? If it is, the harmonic also is; if
the harmonic isn't, then it isn't. It's really a question
of definition. The classical academic definition (at least
according to a quick search on the net---so absolutely no
guarantees) of tail recursion seems to be: "A recursive
function is said to be tail recursive if there are no
pending operations to be performed on return from a
recursive call.", and another site says that "The basic idea
behind tail Recursion is to eliminate the storage of any
state information across the recursive steps." According to
these, factorial isn't tail recursive, because there's a
multiplication operation in suspence when the funtion calls
itself, and state information (the n which will be
multiplied) is required accross the recursive call. As Pete
has pointed out informally, and Andrey more formally, this
is one of those academic definitions which are totally
useless in practice, because they don't add anything to the
understanding, nor to what we can do. In practice, the
important point is the one Andrey made: that the total state
that must be saved must be constant, independant of number
of recursions. In such cases, any compiler which does "tail
recursion optimization" will be able to apply it, regardless
of whether the pedants decide to call it tail recursion or
not.

The strict tail recursion definition is not useless at all.

Let's say that it's only useful if the language (or the
implementors of the language) decide to make it so. Formally
(and in C++), the definition Andrey gave is more useful: if your
code conforms to his contraints, it can potentially be optimized
to eliminate the recursion; if it doesn't, then eliminating the
recursive call will require implementing some sort of stack
("recursion" ) manually, which defeats the space optimization.
Potentially; whether a compiler does so or a language requires
it is another question.

It is used by many functional programmers. This is an
important concept to avoid stack overflow / boost performances
as most compilers will implement TCE, and I mean true TCE,
there are optimizations that transform non- tail recursions to
tail ones before applying TCE, but less compilers do it.

I think in some languages, the language specification requires
tail recusion optimization. Since identifying what you call
tail recursion is trivial, both from a formal and from a
practical point of view, it's not unreasonable for a language to
require it. Since identifying all possible tail recursions
(using the wider definition) is far from trivial (and may even
be undecidable), no language will ever require it. Somewhere
between the two, who knows.

That's why functional programmers use techniques like the one
given by Danny Woods.

One would hope it was only used when the language didn't support
looping otherwise. In such cases, you *must* have a guarantee
that the optimization is applied.

Since we are on a C++ newsgroup, let's talk about C++
compilers and their behavior when confronted with the
factorial recursive function :

I suspect most don't even check for it in the most trivial
cases. In C++, you have very powerful looping constructs, and
it isn't idiomatic to use recursion (tail or otherwise) when
there is a simple solution using a loop. So typically, the
compiler is just wasting time checking for it.

Also, as I mentionned elsewhere, the presence of non-trivial
destructors which must be called *after* the return value has
been copied out adds to the complexity, and reduces the
probability that the optimization could be applied.

int fac (int n)
{
if (n==0)
return 1;
else
return fac(n-1) * n;
}

VC++9 won't apply TCE while GCCv4 will.

It would be interesting to see if there are any cases of
compilers which apply TCE only for what you call tail recursion,
and not in this case.

C++ is not a functional language. It has different idioms. And
compiler optimization should be tuned to the common idioms of
the language it is optimizing. A compiler for Scheme, or any of
the other Lisp dialects, would be seriously deficient if it
didn't apply TCE. In a compiler for C++, on the other hand, I'd
say that checking whether TCE could be applied is a waste of
time. The only time you'd write factoriel like that in C++
would be as a demonstration of recursion; in normal code, you'd
write the iterative solution directly.

But if, as a functional programmer, we use an accumlulator to
obtain TRUE tail recursion (from the academic definition) :

int fac (int n, int acc)
{
if (n==0)
return acc;
else
return fac(n-1, acc*n );
}

then both VC++ and GCC will apply TCE.

Interesting. I'd have expected neither. (On the other hand,
Sun CC also does both, so maybe the compiler writers have found
a justification I'm unaware of.)

And in functional languages, the situation is more chaotic.
The only sure way to get TCE is to implement *true* tail
recursion.

The only sure way in some functional languages, probably.
There's no sure way in C++. The way to do this in C++ is to
write whatever is most natural, without worrying about whether
the compiler will find tail recursion or not, and then, if the
profiler shows it's too slow, optimize manually (probably
eliminating the recursion).

--
James Kanze (GABI Software) email:james.kan ze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

[gpderetta]

Re: is it tail recursion

On Nov 5, 12:25 pm, James Kanze <james.ka...@gm ail.comwrote:

On Nov 4, 4:04 pm, courp...@gmail. com wrote:
>

But if, as a functional programmer, we use an accumlulator to
obtain TRUE tail recursion (from the academic definition) :
int fac (int n, int acc)
{
    if (n==0)
        return acc;
    else
        return fac(n-1, acc*n );
}
then both VC++ and GCC will apply TCE.

>
Interesting.  I'd have expected neither.  (On the other hand,
Sun CC also does both, so maybe the compiler writers have found
a justification I'm unaware of.)
>

I wouldn't be surprised if the justification was getting higher scores
in some benchmark suite that has some tail recursion optimization
opportunity.

IMHO tail recursion is worth something only if the language spec
explicitly requires it.

--
gpd

[courpron@gmail.com]

Re: is it tail recursion

On 5 nov, 12:25, James Kanze <james.ka...@gm ail.comwrote:

On Nov 4, 4:04 pm, courp...@gmail. com wrote:

The strict tail recursion definition is not useless at all.

>
Let's say that it's only useful if the language (or the
implementors of the language) decide to make it so.  Formally
(and in C++), the definition Andrey gave is more useful: if your
code conforms to his contraints, it can potentially be optimized
to eliminate the recursion; if it doesn't, then eliminating the
recursive call will require implementing some sort of stack
("recursion" ) manually, which defeats the space optimization.
Potentially; whether a compiler does so or a language requires
it is another question.

Well, Andrey was talking about a property of some recursive
algorithms. At the end of his message, he talks about tail-recursive
algorithms that can be convertible into iterative ones *in the most
obvious way*. IMO, that's correct and is not outside the strict tail
recursion definition. Converting a (true) tail-recursion to an
iteration is a matter of transforming the function call into a jump
(simple tail call elimination) + reusing the stack, all of this
without any prior non-tail to tail conversion. This is the simplest
way to convert a recursion to an interation.
By the way, I should have used the term "tail recursion elimination"
instead of "tail call elimination" which is more general.

I think in some languages, the language specification requires
tail recusion optimization.  

True. In Scheme the standard R6RS says : [5.11] "Implementation s of
Scheme must be properly tail-recursive. [...] A Scheme implementation
is properly tail-recursive if it supports an unbounded number of
active tail calls." Of course, that doesn't explicitly requires
compilers to do a tail recursion elimination, but those must at least
provide an implementation that does not generate stack overflow.

Since identifying what you call
tail recursion is trivial, both from a formal and from a
practical point of view, it's not unreasonable for a language to
require it.  Since identifying all possible tail recursions
(using the wider definition) is far from trivial (and may even
be undecidable), no language will ever require it.  Somewhere
between the two, who knows.
>
[...]
>

int fac (int n)
{
    if (n==0)
        return 1;
    else
        return fac(n-1) * n;
}
VC++9 won't apply TCE while GCCv4 will.

>
It would be interesting to see if there are any cases of
compilers which apply TCE only for what you call tail recursion,
and not in this case.
>
C++ is not a functional language.  It has different idioms.  And
compiler optimization should be tuned to the common idioms of
the language it is optimizing.  A compiler for Scheme, or any of
the other Lisp dialects, would be seriously deficient if it
didn't apply TCE.  In a compiler for C++, on the other hand, I'd
say that checking whether TCE could be applied is a waste of
time.  The only time you'd write factoriel like that in C++
would be as a demonstration of recursion; in normal code, you'd
write the iterative solution directly. [...]

Yes, and my code examples are just that : a demonstration of
recursion. In no way I wanted to promote, for example, the use of an
accumulator to obtain tail recursion in C++. C++ has alternative and
more suited constructs for this. Furthermore, as you pointed out with
the example of non-trivial destructor, it may be more difficult for a C
++ programmer to determine whether a function is tail-recursive or
not.

In fact, I wanted to show that, in practice, strict tail recursions
are more optimized than other recursions, even those that can also be
converted into an iteration. I guess that some C/C++ compilers provide
tail recursion optimization because those languages are focused on
performances, and (strict) tail recursion elimination is not that hard
to implement. Concerning other non-functionnal languages, I don't
really know. Some java JVMs now support tail recursion optimization
while it was not the case a few years ago : as a consequence it's
possible to have tail recursion optimized by some JVMs and not by
others. So relying on tail recursion optimization is, indeed, a matter
of programming paradigm, in this case functionnal programming.


Alexandre Courpron.

[Stephen Horne]

Re: is it tail recursion

On Mon, 3 Nov 2008 20:52:55 -0800 (PST), Muzammil
<muzammilPeer98 7@gmail.comwrot e:

>ok explain me this one .

>int factorial (int n)
>{
>if (n==0) return 1;
>else
>factorail(n-1)*n;
>}
>
>why this recursion is tail recursion and harmonic is not.

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_inter nal (int p_So_Far, int n)
{
if (n == 0) return 1;
return factorial_inter nal (p_So_Far * n, n - 1);
}

int factorial (int n)
{
return factorial_inter nal (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 ;-)

[Stephen Horne]

Re: is it tail recursion

On Thu, 06 Nov 2008 03:13:28 +0000, Stephen Horne
<sh006d3592@blu eyonder.co.ukwr ote:

>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.

Whoops - this is exactly what functional types call tail recursion (or
more accurately, tail call) elimination. C and C++ are doing nothing
different in this respect.

I'll get back to you later with the excuse for why it wasn't stupid to
say that - it's going to take a fair bit of creative thinking ;-)


The point about stack use and references to local variables stands,
however. C and C++ compilers have to be pessimistic about validity in
cases where most functional languages guarantee to optimise tail
calls.