By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
455,434 Members | 1,878 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 455,434 IT Pros & Developers. It's quick & easy.

is it tail recursion

P: n/a
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.

Nov 3 '08 #1
Share this Question
Share on Google+
35 Replies


P: n/a
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...tail+recursion

Regards.
Nov 3 '08 #2

P: n/a
On 2008-11-03 03:55:06 -0500, Muzammil <mu*************@gmail.comsaid:
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.
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.

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

Nov 3 '08 #3

P: n/a
On 2008-11-03 06:18:44 -0500, al**********@gmail.com 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...tail+recursion

Regards.
Most compilers ought to be able to optimize the original code into a
loop by recognizing the tail recursion. It's not a matter of returning
exactly the value returned by the recursive call (that would be a very
small set of functions, all useless), but of whether the recursive call
can be changed into a loop. An example that can't is Ackerman's
function:

int ackerman(unsigned i, unsigned j)
{
if (i == 0)
return j + 1;
else if (j == 0)
return ackerman(i - 1, 1);
else
return ackerman(i - 1, ackerman(i, j - 1));
}

The result depends on multiple recursive calls, so the function can't
be transformed into a simple loop. It also grows very quickly; watch
out for overflows.

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

Nov 3 '08 #4

P: n/a
Thank you for the clarification.
Nov 3 '08 #5

P: n/a
On Nov 3, 12:42*pm, Pete Becker <p...@versatilecoding.comwrote:
On 2008-11-03 03:55:06 -0500, Muzammil <muzammilPeer...@gmail.comsaid:
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.

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

--
Max
Nov 3 '08 #6

P: n/a
Pete Becker <pe**@versatilecoding.comwrites:
On 2008-11-03 03:55:06 -0500, Muzammil <mu*************@gmail.comsaid:
>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.

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.
Nov 3 '08 #7

P: n/a
On 2008-11-03 09:10:30 -0500, Maxim Yegorushkin
<ma***************@gmail.comsaid:
On Nov 3, 12:42┬*pm, Pete Becker <p...@versatilecoding.comwrote:
>On 2008-11-03 03:55:06 -0500, Muzammil <muzammilPeer...@gmail.comsaid:
>>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.

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:
Yes.
>
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().
Shrug. Think about how to turn this into a loop.

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

Nov 3 '08 #8

P: n/a
On 2008-11-03 11:33:23 -0500, Danny Woods <da********@yahoo.co.uksaid:
>
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.
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.
>
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.

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

Nov 3 '08 #9

P: n/a
Pete Becker <pe**@versatilecoding.comwrites:
On 2008-11-03 11:33:23 -0500, Danny Woods <da********@yahoo.co.uksaid:
>>
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.
Nov 3 '08 #10

P: n/a
On Mon, 3 Nov 2008 11:45:39 -0500, Pete Becker
<pe**@versatilecoding.comwrote:
>On 2008-11-03 11:33:23 -0500, Danny Woods <da********@yahoo.co.uksaid:
>>
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.
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.

Nov 3 '08 #11

P: n/a
On Mon, 03 Nov 2008 18:18:34 +0000, Stephen Horne
<sh********@blueyonder.co.ukwrote:
>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?

Nov 3 '08 #12

P: n/a
On 2008-11-03 11:58:02 -0500, Danny Woods <da********@yahoo.co.uksaid:
Pete Becker <pe**@versatilecoding.comwrites:
>On 2008-11-03 11:33:23 -0500, Danny Woods <da********@yahoo.co.uksaid:
>>>
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.
And that's an optimization that's known as "tail recursion
elimination". Compilers have been doing it for years.
>
>>
>>>
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.
Since this is a C++ forum, that's probably appropriate. <gAs I said,
C compilers were doing tail recursion elimination on code like the
original example at least twenty years ago.

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

Nov 3 '08 #13

P: n/a
On 2008-11-03 13:18:34 -0500, Stephen Horne <sh********@blueyonder.co.uksaid:
On Mon, 3 Nov 2008 11:45:39 -0500, Pete Becker
<pe**@versatilecoding.comwrote:
>On 2008-11-03 11:33:23 -0500, Danny Woods <da********@yahoo.co.uksaid:
>>>
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.

Not true - it is *the* standard definition, and the whole point of
defining *tail* recursion as a special case of recursion.
Gosh, I guess the C compilers that have been doing "tail recursion
elimination" on code like the original example must have been wrong.
>
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.
Well, that sometimes happens when parochial world views meet up with reality.
>
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.
C compilers have been doing tail recursion elimination for at least
twenty years on code like the original example.
>
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.
Certainly not, because it's not needed.

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

Nov 3 '08 #14

P: n/a
On Mon, 3 Nov 2008 13:29:48 -0500, Pete Becker
<pe**@versatilecoding.comwrote:
>Not true - it is *the* standard definition, and the whole point of
defining *tail* recursion as a special case of recursion.

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.
> goto myfunction (params);
>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.

Nov 3 '08 #15

P: n/a
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
Nov 4 '08 #16

P: n/a
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
Nov 4 '08 #17

P: n/a
Muzammil <mu*************@gmail.comwrites:
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.
Nov 4 '08 #18

P: n/a
On Nov 4, 5:52 am, Muzammil <muzammilPeer...@gmail.comwrote:
On Nov 4, 6:33 am, Andrey Tarasevich
<andreytarasev...@hotmail.comwrote:
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:ja*********@gmail.com
Conseils en informatique orientÚe objet/
Beratung in objektorientierter Datenverarbeitung
9 place SÚmard, 78210 St.-Cyr-l'╔cole, France, +33 (0)1 30 23 00 34
Nov 4 '08 #19

P: n/a
Danny Woods <da********@yahoo.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.
Nov 4 '08 #20

P: n/a
On 4 nov, 10:25, James Kanze <james.ka...@gmail.comwrote:
On Nov 4, 5:52 am, Muzammil <muzammilPeer...@gmail.comwrote:

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.
Nov 4 '08 #21

P: n/a
On Nov 4, 3:25*am, James Kanze <james.ka...@gmail.comwrote:
On Nov 4, 5:52 am, Muzammil <muzammilPeer...@gmail.comwrote:
On Nov 4, 6:33 am, Andrey Tarasevich
<andreytarasev...@hotmail.comwrote:
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

Nov 4 '08 #22

P: n/a
On 2008-11-04 10:04:36 -0500, co******@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)

Nov 4 '08 #23

P: n/a
On 4 nov, 17:28, Pete Becker <p...@versatilecoding.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.
Nov 4 '08 #24

P: n/a
On 2008-11-04 11:58:49 -0500, co******@gmail.com said:
On 4 nov, 17:28, Pete Becker <p...@versatilecoding.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)

Nov 4 '08 #25

P: n/a
On Nov 4, 4:04 pm, courp...@gmail.com wrote:
On 4 nov, 10:25, James Kanze <james.ka...@gmail.comwrote:
On Nov 4, 5:52 am, Muzammil <muzammilPeer...@gmail.comwrote:
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:ja*********@gmail.com
Conseils en informatique orientÚe objet/
Beratung in objektorientierter Datenverarbeitung
9 place SÚmard, 78210 St.-Cyr-l'╔cole, France, +33 (0)1 30 23 00 34
Nov 5 '08 #26

P: n/a
On Nov 5, 12:25*pm, James Kanze <james.ka...@gmail.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
Nov 5 '08 #27

P: n/a
On 5 nov, 12:25, James Kanze <james.ka...@gmail.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] "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.
Nov 5 '08 #28

P: n/a
On Mon, 3 Nov 2008 20:52:55 -0800 (PST), Muzammil
<mu*************@gmail.comwrote:
>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_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 ;-)

Nov 6 '08 #29

P: n/a
On Thu, 06 Nov 2008 03:13:28 +0000, Stephen Horne
<sh********@blueyonder.co.ukwrote:
>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.

Nov 6 '08 #30

P: n/a
On Wed, 5 Nov 2008 03:25:38 -0800 (PST), James Kanze
<ja*********@gmail.comwrote:
>On Nov 4, 4:04 pm, courp...@gmail.com wrote:
>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).
Even in functional languages, it's easy to make mistakes - to think
something is true tail recursion when it is not, and get a broken
program (which still probably passes unit testing) as a result.

Which is why I think tail call optimisation should be explicitly
requested when needed. It's not just an optimisation - it's a
correctness issue.

In C++, though, not a big deal - the assumption of tail call
optimisation isn't there and, as you say, the idioms are different.

Nov 6 '08 #31

P: n/a
James Kanze wrote:
On Nov 4, 4:04 pm, courp...@gmail.com wrote:
[...]
>int fac (int n)
{
if (n==0)
return 1;
else
return fac(n-1) * n;
}
>VC++9 won't apply TCE while GCCv4 will.

[...] 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.
OTOH, on 32bit architectures 'int' will overflow at 16!,
which is long before you run into stack problems, so on
these architectures I don't see a need to not to apply
the use the most obvious implementation of factorial. it
would seem premature optimization to me.
[...]
Schobi
Nov 6 '08 #32

P: n/a
On 2008-11-05 22:32:19 -0500, Stephen Horne <sh********@blueyonder.co.uksaid:
On Tue, 4 Nov 2008 11:28:02 -0500, Pete Becker
<pe**@versatilecoding.comwrote:
>What happens if you write the return statement as:

return n * fac(n-1);

Don't focus so much on the ordering in the source code.
Sigh. The text that you snipped described an optimization that certain
compilers did, and my question was specifically about how a small
variation in the code affected that optimization.

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

Nov 6 '08 #33

P: n/a
On Thu, 06 Nov 2008 10:32:45 +0100, Hendrik Schober <sp******@gmx.de>
wrote:
OTOH, on 32bit architectures 'int' will overflow at 16!,
which is long before you run into stack problems, so on
these architectures I don't see a need to not to apply
the use the most obvious implementation of factorial. it
would seem premature optimization to me.
The basic issue is that you're unlikely to use a simple factorial for
32 bit integers anyway.

The factorial is mostly a building block for defining other, more
directly useful functions. An obvious example would be counting
combinations or permutations. Those more useful functions often have
large numbers of cases where the factorial goes out of bounds, but the
needed result doesn't - often because one factorial is divided by
another. An iterative solution that does the whole job at once is both
more efficient and less prone to overflow.

That is, instead of...

int somefunc (int p1, int p2)
{
return factorial (p1) / factorial (p2);
}

You'd more likely have...

int somefunc (int p1, int p2)
{
int temp = 1;
for (int i = p2+1; i <= p1; ++i) temp *= i;
return temp;
}

If you are doing this kind of thing for anything serious, of course,
you're probably using a big integer library. Still quite hard to
overflow the stack using recursion, but possible - the maximum size of
the stack isn't all that big in general.
Besides, the real point of the factorial function is only to
illustrate a principle. Real world functions that require tail
recursion elimination would generally not have that problem.

Another common illustration from the functional world would be a
simple list summary such as an 'any' function...

struct bool_list_node
{
bool_list_node* m_link;
bool m_value;
};

bool any (bool_list_node* p)
{
if (p == 0) return false;
if (p->m_value) return true;

return any (p->m_link);
}

The tail recursion here has no numeric overflow issues, but could
easily overrun the stack. Fortunately, this is not the kind of code
that C++ programmers would normally write.

And in truth, you wouldn't normally write that in a functional
language either - you'd use a library 'any' function, or maybe a
'fold' or 'reduce' function. It's still just a simple illustration of
a principle.

Nov 6 '08 #34

P: n/a
On Nov 5, 9:32*pm, Stephen Horne <sh006d3...@blueyonder.co.ukwrote:
It's even more immediately
obvious in Forth, though I have no idea whether Forth compilers do
tail call elimination.

It's reasonably common in Forth compilers that generate direct
threaded code in batch mode. It's not so much tail recursion
elimination, but rather the optimization of tail calls in general (IOW
replacing the final CALL/RET in a word with a JMP), if the compiler
can tell that the called words don't care about the contents of the
return stack at entry. Since the return stack is exposed in Forth,
the called word can look to see what's on top of the return stack,
which will obviously be different in the CALL/RET and JMP cases.
Fortunately the vast majority of words do not, and only use the return
stack for additional local data storage - loop counters are
particularly popular.
Nov 6 '08 #35

P: n/a
Stephen Horne wrote:
On Thu, 06 Nov 2008 10:32:45 +0100, Hendrik Schober <sp******@gmx.de>
wrote:
> OTOH, on 32bit architectures 'int' will overflow at 16!,
which is long before you run into stack problems, so on
these architectures I don't see a need to not to apply
the use the most obvious implementation of factorial. it
would seem premature optimization to me.

The basic issue is that you're unlikely to use a simple factorial for
32 bit integers anyway.
Yeah. Sorry for nitpicking.
[...]
Schobi
Nov 7 '08 #36

This discussion thread is closed

Replies have been disabled for this discussion.