«

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.

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.

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.

In article < .com>,
"Aloo" <> 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.

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

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.

In article <>,
Michael Mair <> 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.

Christian Bau wrote:
> In article <>,
> Michael Mair <> 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.