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

inline int factorial(int n)
{
    if(!n) return 1;
    else return n*factorial(n-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).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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