递归函数可以内联吗？

Question

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

在我阅读本文时,发现如果编译器没有正确处理上述代码会导致"无限编译".

编译器如何决定是否内联函数？

Answer 1

首先,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个).

Answer 2

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

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

对于案例2,许多编译器都#pragma可以设置为指定应该执行此操作的最大深度.在gcc中,您也可以从命令行传入此命令--max-inline-insns-recursive(请参阅此处的更多信息).

Answer 3

如果可能,AFAIK GCC将对递归函数执行尾调用消除.但是你的函数不是尾递归的.

Answer 4

编译器创建一个调用图; 当检测到一个循环调用自身时,该函数在某个深度后不再内联(n = 1,10,100,无论编译器调到哪个).