Может ли рекурсивная функция быть встроенной?

Question

Может ли рекурсивная функция быть встроенной?

inline int factorial(int n)

{

    if(!n) return 1;

    else return n*factorial(n-1);

}

Как я читал этой, установлено, что приведенный выше код приведет к "бесконечной компиляции", если не правильно обрабатывается компилятором.

как компилятор решает, следует ли встроить функцию или нет ?

547 9

c compiler-construction

9 ответов:

Comments

Ничего не найдено.

Derek Park · Accepted Answer · 2008-10-10 08:47:13

сначала 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 раза. Некоторые компиляторы do выполнить такую оптимизацию. Я помню, что MSVC++ имеет настройку для настройки уровня встраивания, которая будет выполняться на рекурсивных функциях (до 20, я считаю).

Matt J · Accepted Answer · 2008-10-10 08:42:29

действительно, если ваш компилятор не действует разумно, он может попытаться вставить копии вашего inlineD функция рекурсивно, создавая бесконечно большой код. Однако большинство современных компиляторов признают это. Они могут либо:

не встроить функцию вообще

встроите его до определенной глубины, и если он не был завершен к тому времени, вызовите отдельный экземпляр вашей функции, используя стандартное соглашение о вызове функции. Это может позаботиться о многих общие случаи в высокопроизводительном образе, пока выходящ запасной вариант для редкого случая с большой глубиной звонока. Это также означает, что вы сохраняете как встроенные, так и отдельные версии кода этой функции.

для случая 2, многие компиляторы имеют #pragmas Вы можете задать, чтобы указать максимальную глубину, на которую это должно быть сделано. В gcc, вы также можете передать это из командной строки с помощью --max-inline-insns-recursive (см. Подробнее здесь).

leppie · Accepted Answer · 2008-10-10 08:56:47

AFAIK GCC будет делать исключение хвостового вызова на рекурсивных функциях, если это возможно. Однако ваша функция не хвост рекурсивной.

Paul Nathan · Accepted Answer · 2008-10-10 08:45:12

компилятор создает граф вызовов; при обнаружении цикла, вызывающего себя, функция больше не встроена после определенной глубины(n=1, 10, 100, независимо от того, на что настроен компилятор).

alex strange · Accepted Answer · 2008-10-16 22:53:55

некоторые рекурсивные функции могут быть преобразованы в циклы, которые эффективно бесконечно подставляет их. Я считаю, что gcc может это сделать, но я не знаю о других компиляторах.

yungchin · Accepted Answer · 2008-10-10 08:50:24

см. уже приведенные ответы, почему это обычно не работает.

в качестве "сноски" вы можете достичь эффекта, который вы ищете (по крайней мере, для факториала, который вы используете в качестве примера), используя метапрограммирование шаблона. Вставка из Википедии:
template <int N>
struct Factorial 
{
    enum { value = N * Factorial<N - 1>::value };
};

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

mattlant · Accepted Answer · 2008-10-10 08:36:45

компилятор сделает график вызовов, чтобы обнаружить такие вещи и предотвратить их. Таким образом, он увидит, что функция вызывает себя, а не встроенную.

но в основном он управляется встроенным ключевым словом и переключателями компилятора(например, вы можете иметь его автоматически встроенные небольшие функции даже без ключевого слова.) Важно отметить, что отладочные компиляции никогда не должны быть встроены, поскольку стек вызовов не будет сохранен для отражения вызовов, созданных в коде.

Windows programmer · Accepted Answer · 2008-10-10 08:50:15

" как компилятор решает, следует ли встроить функцию или нет ?"

Это зависит от компилятора, параметров, которые были указаны, номера версии компилятора, возможно, сколько памяти доступно и т. д.

исходный код программы по-прежнему должен подчиняться правилам для встроенных функций. Независимо от того, будет ли функция встроена, вы должны подготовиться к возможности того, что она будет встроена (некоторое неизвестное количество раз).

в Заявление Википедии о том, что рекурсивные макросы обычно являются незаконными, выглядит довольно плохо информированным. C и C++ предотвращают рекурсивные вызовы, но единица перевода не становится незаконной, содержа макрокод, который выглядит так, как будто он был бы рекурсивным. В монтажники, рекурсивные макросы, как правило, юридическое.

Roger Nelson · Accepted Answer · 2008-10-17 08:08:58

некоторые компиляторы (т. е. Borland C++) не имеют встроенного кода, содержащего условные операторы (if, case, while и т. д..) таким образом, рекурсивная функция в вашем примере не будет встроена.