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

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

Answer 2

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

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

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

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

См. Ответы, которые уже даны, почему это обычно не работает.

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

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

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

Answer 7

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

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

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

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

Answer 8

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

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

Answer 9

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