CODEWITHSUNDEEP
c++cinline-functions
Ashwin
Ashwin

Reputation: 1643

Can a recursive function be inline?

inline int factorial(int n)
{
    if(!n) return 1;
    else return n*factorial(n-1);
}

As I was reading this, found that the above code would lead to "infinite compilation" if not handled by compiler correctly.

How does the compiler decide whether to inline a function or not ?

Upvotes: 160

Views: 56798

Answers (9)

Roger Nelson
Roger Nelson

Reputation: 1912

Some compilers (I.e. Borland C++) do not inline code that contains conditional statements (if, case, while etc..) so the recursive function in your example would not be inlined.

Upvotes: 0

alex strange
alex strange

Reputation: 1249

Some recursive functions can be transformed into loops, which effectively infinitely inlines them. I believe gcc can do this, but I don't know about other compilers.

Upvotes: 4

leppie
leppie

Reputation: 117300

AFAIK GCC will do tail call elimination on recursive functions, if possible. Your function however is not tail recursive.

Upvotes: 8

yungchin
yungchin

Reputation: 1599

See the answers already given for why this won't typically work.

As a "footnote", you could achieve the effect you're looking for (at least for the factorial you're using as an example) using template metaprogramming. Pasting from Wikipedia:

template <int N>
struct Factorial 
{
    enum { value = N * Factorial<N - 1>::value };
};

template <>
struct Factorial<0> 
{
    enum { value = 1 };
};

Upvotes: 3

Windows programmer
Windows programmer

Reputation: 8065

"How does the compiler decide whether to inline a function or not ?"

That depends on the compiler, the options that were specified, the version number of the compiler, maybe how much memory is available, etc.

The program's source code still has to obey the rules for inlined functions. Whether or not the function gets inlined, you have to prepare for the possibility that it will be inlined (some unknown number of times).

The Wikipedia statement that recursive macros are typically illegal looks rather poorly informed. C and C++ prevent recursive invocations but a translation unit doesn't become illegal by containing macro code that looks like it would have been recursive. In assemblers, recursive macros are typically legal.

Upvotes: 1

Derek Park
Derek Park

Reputation: 46856

First, the inline specification on a function is just a hint. The compiler can (and often does) completely ignore the presence or absence of an inline qualifier. With that said, a compiler can inline a recursive function, much as it can unroll an infinite loop. It simply has to place a limit on the level to which it will "unroll" the function.

An optimizing compiler might turn this code:

inline int factorial(int n)
{
    if (n <= 1)
    {
        return 1;
    }
    else
    {
        return n * factorial(n - 1);
    }
}

int f(int x)
{
    return factorial(x);
}

into this code:

int factorial(int n)
{
    if (n <= 1)
    {
        return 1;
    }
    else
    {
        return n * factorial(n - 1);
    }
}

int f(int x)
{
    if (x <= 1)
    {
        return 1;
    }
    else
    {
        int x2 = x - 1;
        if (x2 <= 1)
        {
            return x * 1;
        }
        else
        {
            int x3 = x2 - 1;
            if (x3 <= 1)
            {
                return x * x2 * 1;
            }
            else
            {
                return x * x2 * x3 * factorial(x3 - 1);
            }
        }
    }
}

In this case, we've basically inlined the function 3 times. Some compilers do perform this optimization. I recall MSVC++ having a setting to tune the level of inlining that would be performed on recursive functions (up to 20, I believe).

Upvotes: 164

Paul Nathan
Paul Nathan

Reputation: 40319

The compiler creates a call graph; when a cycle is detected calling itself, the function is no longer inlined after a certain depth(n=1, 10, 100, whatever the compiler is tuned to).

Upvotes: 7

Matt J
Matt J

Reputation: 45223

Indeed, if your compiler does not act intelligently, it may try inserting copies of your inlined function recursively, creating infinitely-large code. Most modern compilers will recognize this, however. They can either:

  1. Not inline the function at all
  2. Inline it up to a certain depth, and if it hasn't terminated by then, call the separate instance of your function using the standard function calling convention. This can take care of many common cases in a high-performance manner, while leaving a fallback for the rare case with a large call depth. This also means that you keep both inlined and separate versions of that function's code around.

For case 2, many compilers have #pragmas you can set to specify the maximum depth to which this should be done. In gcc, you can also pass this in from the command-line with --max-inline-insns-recursive (see more info here).

Upvotes: 28

mattlant
mattlant

Reputation: 15451

The compiler will make a call graph to detect these sorts of things and prevent them. So it would see that the function calls itself and not inline.

But mainly it is controlled by the inline keyword and compiler switches(For example, you can have it auto inline small functions even without the keyword.) Its important to note that Debug compilations should never be inlining as the callstack will not be preserved to mirror the calls you created in code.

Upvotes: 1

Related Questions