递归函数可以内联吗?

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 ?

编译器如何决定是否内联一个函数?

9 个解决方案

#1

131

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

在这种情况下，我们基本上把函数内联了3次。有些编译器执行这种优化。我记得msvc++有一个设置来调整在递归函数上执行的内联的级别(我认为是20个)。

#2

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:

实际上，如果编译器没有智能地操作，它可能会尝试递归地插入内联函数的副本，从而创建非常大的代码。然而，大多数现代编译器都会认识到这一点。他们可以:

Not inline the function at all
完全不内联函数
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).

对于案例2，许多编译器都有#pragmas，您可以设置为指定应该达到的最大深度。在gcc中，您还可以使用—max-inline-insns- recursive.com递归从命令行传递这个消息(请参阅这里的更多信息)。

#3

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

如果可能的话，AFAIK GCC将在递归函数上执行尾部调用消除。但是你的函数不是尾部递归的。

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

编译器创建一个调用图;当检测到一个循环调用自身时，函数在一定的深度之后不再内联(n= 1,10,100，无论编译器调到什么)。

#5

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.

一些递归函数可以转化为循环，从而有效地无限地将它们内插。我相信gcc可以做到这一点，但是我不知道其他的编译器。

#6

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

#7

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.

但它主要是由内联关键字和编译器开关控制的(例如，即使没有关键字，也可以让它自动内联小函数)。需要注意的是，调试编译不应该内联，因为调用堆栈不会被保留以反映您在代码中创建的调用。

#8

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

在*的声明中，递归宏通常是非法的，看起来很糟糕。C和c++可以防止递归调用，但是通过包含看起来应该是递归的宏代码，翻译单元不会变得非法。在汇编程序中，递归宏通常是合法的。

#9

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.

有些编译器(例如Borland c++)不使用包含条件语句的内联代码(if、case、while等)，因此示例中的递归函数不会内联。

#1

131