inline recursive functions

Discussion in 'C Programming' started by Aloo, Oct 22, 2005.

  1. Aloo

    Aloo Guest

    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, Oct 22, 2005
    #1
    1. Advertising

  2. Aloo

    Michael Mair Guest

    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, Oct 22, 2005
    #2
    1. Advertising

  3. Aloo

    Skarmander Guest

    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.
    Skarmander, Oct 22, 2005
    #3
  4. In article <>,
    "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.
    Christian Bau, Oct 22, 2005
    #4
  5. Aloo

    Aloo Guest

    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
    Aloo, Oct 23, 2005
    #5
  6. Aloo

    Michael Mair Guest

    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.
    Michael Mair, Oct 23, 2005
    #6
  7. 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, Oct 23, 2005
    #7
  8. Aloo

    Michael Mair Guest

    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.
    Michael Mair, Oct 23, 2005
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    3
    Views:
    447
  2. Daniel Vallstrom
    Replies:
    2
    Views:
    1,830
    Kevin Bracey
    Nov 21, 2003
  3. Digital Puer

    Inline recursive functions?

    Digital Puer, May 1, 2007, in forum: C++
    Replies:
    5
    Views:
    1,253
    Lionel B
    May 1, 2007
  4. Rahul
    Replies:
    3
    Views:
    442
    James Kanze
    Feb 28, 2008
  5. vamsi
    Replies:
    21
    Views:
    2,045
    Keith Thompson
    Mar 9, 2009
Loading...

Share This Page