Can a recursive function be inline?

Question

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 ?

Answer 1

A recursive function could be inlined into other functions, but it cannot be inlined into itself. If it was, it'd end up infinitely recursing at compile-time, a Bad Thing (TM).

Answer 2

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.

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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

Answer 8

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

Answer 9

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.

Answer 10

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.