inline recursive functions

[Aloo]

Dear friends,

If we declare a recursive function as 'inline' then does it actually
convert to an iterative form during compilation ( the executable code
is iterative)?

Is it possible ?

Please reply.

[Michael Mair]

Aloo wrote:

Dear friends,
We are? Nice to know. I'll call upon that.
If we declare a recursive function as 'inline' then does it actually
convert to an iterative form during compilation ( the executable code
is iterative)?
The implementation/compiler has only to make the program behave
as if you have recursion. The inline keyword only is a recommendation
for the compiler but does not change the semantics.

Is it possible ?
Certainly. There may be cases where the compiler effectively makes
your program output the solution to a problem you tackled with a
lengthy program. As long as there is no visible difference, the
compiler may do pretty much everything, even that.

BTW: Code generators outputting C code often are in a better
position to recognize and optimize things like that than compilers.

Please reply.

Done.
Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.

[Skarmander]

Michael Mair wrote:

Aloo wrote:

If we declare a recursive function as 'inline' then does it actually
convert to an iterative form during compilation ( the executable code
is iterative)?

The implementation/compiler has only to make the program behave
as if you have recursion. The inline keyword only is a recommendation
for the compiler but does not change the semantics.

Is it possible ?

Certainly. There may be cases where the compiler effectively makes
your program output the solution to a problem you tackled with a
lengthy program. As long as there is no visible difference, the
compiler may do pretty much everything, even that.

BTW: Code generators outputting C code often are in a better
position to recognize and optimize things like that than compilers.

Yes, but then you're presumably talking about code generators generating
from something that isn't C, which renders the issue moot.

I've seen C compilers that do, in fact, optimize certain tail-recursive
functions to iterative ones and can subsequently inline the result.
Doing it in all cases requires global code analysis and is unattractive
or unfeasible, depending on your platform. This is presumably where the
generators come in: if they generate all code, they could slip in such
analysis while they're at it.

This optimization tactic isn't widely seen in compilers because it's too
clever to pay off in practice; actual C code doesn't use tail-recursive
functions often (of the kind that readily admits optimization), if the
inlining is critical a programmer would never rely on a compiler's
ability to unfold tail recursion, and if the inlining is not critical,
who cares?

Compare this with Scheme compilers, which are *required* to optimize
tail recursion in all cases -- but then, this is because recursion is
the bread and butter of functional languages, and because such
optimization is actually feasible.

S.

[Christian Bau]

In article <11**********************@g44g2000cwa.googlegroups .com>,
"Aloo" <an************@rediffmail.com> wrote:

Dear friends,

If we declare a recursive function as 'inline' then does it actually
convert to an iterative form during compilation ( the executable code
is iterative)?

"inline" is a hint to the compiler, telling it that you wish calls to
this function to be as fast as possible, even if this means growing code
size. Everything else is up to the compiler.

[Aloo]

Dear Michael ,

The code compiles succesfully, but does the compiler know at compile
time at how many places to insert the code, since the number of times
the code executes depends upon the input at runtime.

Is there any method to Actually debug the executed code and see for
myself whether it is recursive or iterative ?

regards

Aloo

[Michael Mair]

Please quote enough context when replying to a message -- otherwise,
people who could give you a good answer if they had the necessary
context cannot do so.

Aloo wrote:
[inlining of recursive functions into iterations?]

The code compiles succesfully, but does the compiler know at compile
time at how many places to insert the code, since the number of times
the code executes depends upon the input at runtime.
Well, there are three possibilities for the special case of everything
known at compile time:
1) The compiler ignored the "inline". This is easiest, thus the most
probable course.
2) The compiler replaced the body of the function by an equivalent
iteration and had to inline only once.
3) The compiler figured out the necessary recursion depth for each and
every call and inserted appropriately many calls. This is the most
unlikely.

In principle, depending on the semantics of your function, all three
are possible for runtime inputs, too, but the latter becomes even
more unlikely (but could still be applicable if the inlined function
is essentially a contraction and there are limits on the processed
type).
The answer to your question depends completely on your compiler and
the compiler settings.
Is there any method to Actually debug the executed code and see for
myself whether it is recursive or iterative ?

Usually not. Many compilers do not generate the same code in debug
mode. Even if they did, the debugger may then seemingly step over
the call of the inlined function.
Certainty can only be gained from looking at the compiler output.
Most compilers give you a chance to do so.
Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.

[Christian Bau]

In article <3s************@individual.net>,
Michael Mair <Mi**********@invalid.invalid> wrote:

Please quote enough context when replying to a message -- otherwise,
people who could give you a good answer if they had the necessary
context cannot do so.

Aloo wrote:
[inlining of recursive functions into iterations?]

The code compiles succesfully, but does the compiler know at compile
time at how many places to insert the code, since the number of times
the code executes depends upon the input at runtime.

Well, there are three possibilities for the special case of everything
known at compile time:
1) The compiler ignored the "inline". This is easiest, thus the most
probable course.
2) The compiler replaced the body of the function by an equivalent
iteration and had to inline only once.
3) The compiler figured out the necessary recursion depth for each and
every call and inserted appropriately many calls. This is the most
unlikely.

Another one: The compiler can generate a function body which inlines up
to a depth of say four, then calls that function body recursively if
necessary. Doing this would eliminate 75% of all the function calls,
while still easy to implement.

[Michael Mair]

Christian Bau wrote:

In article <3s************@individual.net>,
Michael Mair <Mi**********@invalid.invalid> wrote:

Please quote enough context when replying to a message -- otherwise,
people who could give you a good answer if they had the necessary
context cannot do so.

Aloo wrote:
[inlining of recursive functions into iterations?]

The code compiles succesfully, but does the compiler know at compile
time at how many places to insert the code, since the number of times
the code executes depends upon the input at runtime.

Well, there are three possibilities for the special case of everything
known at compile time:
1) The compiler ignored the "inline". This is easiest, thus the most
probable course.
2) The compiler replaced the body of the function by an equivalent
iteration and had to inline only once.
3) The compiler figured out the necessary recursion depth for each and
every call and inserted appropriately many calls. This is the most
unlikely.

Another one: The compiler can generate a function body which inlines up
to a depth of say four, then calls that function body recursively if
necessary. Doing this would eliminate 75% of all the function calls,
while still easy to implement.

Thank you -- did not think of that :-)

Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.