is it tail recursion

[Muzammil]

int harmonic(int n) {
if (n=1) {
return 1;
}
else {
return harmonic(n-1)+1/n;
}
}

can any help me ??
Is it Tail Rercursion??
i just want the answer about tail recursion and and some examples
of tail recursion so that i can differentiate between tail and non-
tail recrsion.

 

[alasham.said]

Hello,

I believe that, by definition, it is not. In the second case the
function does not return _exactly_ the value returned by a recursive
call (there is an addition and a division operation that have to be
performed before returning the value).

For definitions, see:
http://www.google.com/search?hl=en&q=define:+tail+recursion

Regards.

 

[alasham.said]

Thank you for the clarification.

 

[Maxim Yegorushkin]

If you change the last line slightly the answer becomes a bit clearer:

return 1/n + harmonic(n-1);

Since the tail of the function is a call to the function, this is tail
recursion.

Is it really? I read this code as:

int tmp1 = harmonic(n-1);
int tmp2 = 1/n;
return tmp1 + tmp2;

I.e. the tail of the function is a call to the built-in operator+(int,
int), not to harmonic().

 

[Danny Woods]

If you change the last line slightly the answer becomes a bit clearer:

return 1/n + harmonic(n-1);

Since the tail of the function is a call to the function, this is tail
recursion. It could be replaced by a simple loop, which is an
optimization that many compilers do.

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

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));
}

which would be kicked off from your API function.

Of course, the types here don't make a lot of sense: (1/n) is going to
be zero for all values of n > 1 thanks to integer rounding.

Usually, tail recursion makes things a little messier to read, but much,
much more efficient in terms of speed and stack space than normal
recursion if your compiler can optimize the function calls away. That
said, plain iteration is generally simpler to understand and doesn't
blow your stack for large numbers of iterations if your compiler does
NOT perform this optmisation, so its generally safer to just iterate.

Cheers,
Danny.

 

[Danny Woods]

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

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.

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.

 

[Stephen Horne]

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.

Not true - it is *the* standard definition, and the whole point of
defining *tail* recursion as a special case of recursion.

The best place to learn about this is in the rationales for the Scheme
programming language. Tail recursion is used a lot in functional
programming languages, and the rumbling noise you heard just after
posting was the sound of all the worlds functional programmers jaws
hitting the ground.

Personally, one of my vaguer maybe-it-would-be-nice wishlist items for
C++ would be some explicit tail recursion mechanism - something that
guarantees the tail recursion optimisation, makes it difficult to mess
up, and spots the problem if you manage to mess up anyway.

One option might be a statement something like...

goto return myfunction (params);

or simply...

goto myfunction (params);

Which in either case should be valid whatever the return type,
including void. Possibly non-recursive and indirectly recursive calls
should also be supported, so long as the return types match.

I doubt anything like this will ever make an appearance in C++,
though.

 

[Stephen Horne]

Which in either case should be valid whatever the return type,
including void. Possibly non-recursive and indirectly recursive calls
should also be supported, so long as the return types match.

I should have said, one problem with allowing non-recursive and
indirectly recursive gotos as call-without-return is that you lose the
ability to auto-detect the problems. After all...

goto myfunc (x, y) + 1;

Who's to say that you weren't intending to goto-call operator+ rather
than myfunc?

 

[Stephen Horne]

Gosh, I guess the C compilers that have been doing "tail recursion
elimination" on code like the original example must have been wrong.

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.

Tail recursion is one very specific and well defined special case -
not the general case, and not any of the many other special cases that
might be useful for some particular purpose.

Certainly not, because it's not needed.

You're missing the point. It's not just an optimisation, it affects
the semantics of the code.

If you explicitly request tail recursion, you are basically specifying
that simple recursion is invalid because there's no guarantee that the
depth of that recursion will stay in reasonable bounds - that you
*require* iterative generated code, but are writing it in a recursive
form for readability/maintainability/simplicity reasons.

Getting a stack overflow doesn't just mean your program is less
efficient than it could be - it means it is broken. Leaving this issue
to the whims of the optimiser seems wrong to me. If you *need* tail
recursion to be converted to an iterative form, you should explicitly
say so.

If it's just an optimisation, of course, it should be left to the
compiler - forcing tail recursion might concievably be the wrong
choice on some platforms.


Of course it's not a big deal - people have been working in C and C++
for decades without being particularly upset about the lack of
explicit tail recursion - but as I said, it's only a vague
maybe-it-would-be-nice thing.

 

[Andrey Tarasevich]

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.

 

[Muzammil]

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.

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]

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_helper(int n, int a)
{
if (n == 0) return a;
else return factorial_helper(n - 1, n * a);
}

int factorial(int n)
{
return factorial_helper(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]

[...]

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.

 

[Danny Woods]

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]

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]

    [...]

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/archive/2008/08/07/understanding-tail-recursion.aspx

 

[courpron]

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.

 

[James Kanze]

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

 

[gpderetta]

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.

 

[courpron]

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] "Implementations 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.