Can a recursive function be inline?

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