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

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

Ответ 2

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

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

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

Ответ 3

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

Ответ 4

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

Ответ 5

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

Ответ 6

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

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

Ответ 7

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

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

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

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

Ответ 8

См. ответы, уже приведенные для того, почему это обычно не работает.

Как "сноска", вы можете достичь эффекта, который вы ищете (по крайней мере, для факториала, который вы используете в качестве примера), используя метапрограммирование шаблонов. Вставка из Википедии:

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

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

Ответ 9

Некоторые компиляторы (I.e. Borland С++) не имеют встроенного кода, который содержит условные операторы (if, case, while и т.д.), поэтому рекурсивная функция в вашем примере не будет встраиваться.