Can a recursive function be inline?

Question

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).

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).

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

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).

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 };
};

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.

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.