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 ?

49850 次浏览
小开

编译器将创建一个调用图来检测这类事情并防止它们发生。所以它会看到函数调用自己而不是内联。

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

小开

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

  1. 根本没有内联函数
  2. 将其内联到一定深度，如果此时它还没有终止，则使用标准函数调用约定调用函数的单独实例。这可以以高性能的方式处理许多常见情况，同时为具有较大调用深度的罕见情况留下备用。这也意味着要保留该函数代码的内联版本和单独版本。

对于情况2，许多编译器都有 #pragma，您可以设置为指定应该执行此操作的最大深度。在 GCC中，还可以使用 --max-inline-insns-recursive从命令行传递这个命令(参见更多信息 给你)。

小开

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

小开
最佳答案

首先，函数的 inline规范只是一个提示。编译器可以(而且经常)完全忽略 inline限定符的存在或不存在。也就是说，编译器 可以内联了一个递归函数，就像它可以展开一个无限循环一样。它只需要对将要“展开”函数的级别设置一个限制。

一个编译器最佳化可能会把这个代码:

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


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

进入这个代码:

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

在这个例子中，我们基本上内联了函数3次。一些编译器 做执行此优化。我记得 MSVC + + 有一个设置来调整在递归函数上执行的内联级别(我相信最多可以达到20)。

小开

“编译器如何决定是否内联函数?”

这取决于编译器、指定的选项、编译器的版本号、可用内存的数量等等。

程序的源代码仍然必须遵守内联函数的规则。无论函数是否被内联，您都必须准备好它被内联的可能性(一些未知的次数)。

Wikipedia 关于递归宏通常是非法的说法看起来信息不足。C 和 C + + 防止递归调用，但是包含看起来像是递归的宏代码的翻译单元不会变得非法。在汇编程序中，递归宏通常是合法的。

小开

看看已经给出的为什么这不会通常工作的答案。

作为一个“脚注”，您可以使用 模板超编程实现所寻找的效果(至少对于您作为示例使用的阶乘)。粘贴维基百科:

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


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

如果可能的话，AFAIK GCC 会对递归函数进行尾部调用消除，但是你的函数不是尾部递归的。

小开

一些递归函数可以转换成循环，这样可以有效地无限内联它们。我相信 gcc 可以做到这一点，但我不知道其他编译器的情况。

小开

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


提交答案