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

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

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

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

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

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

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

Во-первых, спецификация функции 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).

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

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

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

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

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

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

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

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

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

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

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