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@gmail.com]

Re: is it tail recursion

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%3A+tail+recursion

Regards.

[Pete Becker]

Re: is it tail recursion

On 2008-11-03 03:55:06 -0500, Muzammil <muzammilPeer98 7@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)

[Pete Becker]

Re: is it tail recursion

On 2008-11-03 06:18:44 -0500, alasham.said@gm ail.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=define%3A+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(unsign ed 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)

[alasham.said@gmail.com]

Re: is it tail recursion

Thank you for the clarification.

[Maxim Yegorushkin]

Re: is it tail recursion

On Nov 3, 12:42 pm, Pete Becker <p...@versatile coding.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

[Danny Woods]

Re: is it tail recursion

Pete Becker <pete@versatile coding.comwrite s:

On 2008-11-03 03:55:06 -0500, Muzammil <muzammilPeer98 7@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.

[Pete Becker]

Re: is it tail recursion

On 2008-11-03 09:10:30 -0500, Maxim Yegorushkin
<maxim.yegorush kin@gmail.comsa id:

On Nov 3, 12:42 pm, Pete Becker <p...@versatile coding.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)

[Pete Becker]

Re: is it tail recursion

On 2008-11-03 11:33:23 -0500, Danny Woods <dannywoodz@yah oo.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)

[Danny Woods]

Re: is it tail recursion

Pete Becker <pete@versatile coding.comwrite s:

On 2008-11-03 11:33:23 -0500, Danny Woods <dannywoodz@yah oo.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.

[Stephen Horne]

Re: is it tail recursion

On Mon, 3 Nov 2008 11:45:39 -0500, Pete Becker
<pete@versatile coding.comwrote :

>On 2008-11-03 11:33:23 -0500, Danny Woods <dannywoodz@yah oo.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.

[Stephen Horne]

Re: is it tail recursion

On Mon, 03 Nov 2008 18:18:34 +0000, Stephen Horne
<sh006d3592@blu eyonder.co.ukwr ote:

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

[Pete Becker]

Re: is it tail recursion

On 2008-11-03 11:58:02 -0500, Danny Woods <dannywoodz@yah oo.co.uksaid:

Pete Becker <pete@versatile coding.comwrite s:
>

>On 2008-11-03 11:33:23 -0500, Danny Woods <dannywoodz@yah oo.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)

[Pete Becker]

Re: is it tail recursion

On 2008-11-03 13:18:34 -0500, Stephen Horne <sh006d3592@blu eyonder.co.uksa id:

On Mon, 3 Nov 2008 11:45:39 -0500, Pete Becker
<pete@versatile coding.comwrote :
>

>On 2008-11-03 11:33:23 -0500, Danny Woods <dannywoodz@yah oo.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)

[Stephen Horne]

Re: is it tail recursion

On Mon, 3 Nov 2008 13:29:48 -0500, Pete Becker
<pete@versatile coding.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.