Два вопроса о встроенных функциях в С++

У меня вопрос, когда я компилирую встроенную функцию в С++.

Может ли рекурсивная функция работать с inline. Если да, пожалуйста, опишите, как это сделать.

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

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

inline f(int n) {
 if(n<=1)
 return 1;
 else {
 n=n*f(n-1);
 return n;
 }
}

как это работает?

Я использую turbo 3.2

Кроме того, если встроенный код функции слишком велик, может ли компилятор автоматически изменить его в нормальной функции?

спасибо

6 ответов

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

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

С GCC 4.4

int fac = f(10);

подготовил эту инструкцию:

movl $3628800, 4(%esp)

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


Я предполагаю, что ваш друг пытался сказать, что если дать константу, компилятор мог бы вычислить результат полностью во время компиляции и просто вставить ответ на сайт вызова. С++ 0x на самом деле имеет механизм для этого с именем constexpr, но существуют ограничения на то, насколько сложным может быть код. Но даже с текущей версией С++ это возможно. Это полностью зависит от компилятора.

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

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

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

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

Если запуск этого кода на вашем ноутбуке занимает очень много времени, то возможно, что вы просто дали ему очень большие значения, и для вычисления ответа просто требуется много времени... Код выглядит нормально, но сохраняйте что значения выше 13! будут переполнять 32-разрядный int. Какую ценность вы пытались передать?

Единственный способ узнать, что на самом деле происходит, - это скомпилировать его для сборки, сгенерированной.

PS: вы можете захотеть изучить более современный компилятор, если вы заинтересованы в оптимизации. Для окон есть MingW и бесплатные версии Visual С++. Для * NIX есть, конечно, g++.

РЕДАКТИРОВАТЬ: есть также функция Tail Recursion Optimization, которая позволяет компиляторам конвертировать определенные типы рекурсивных алгоритмы к итеративным, что делает их лучшими кандидатами для встраивания. (В дополнение к тому, чтобы сделать их более эффективным для стека).


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

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

Что вы пытаетесь сказать о своем примере, что "ничего не отображает" также неясно. В коде нет ничего, что могло бы "отобразить" что угодно. Неудивительно, что "ничего не отображает". Кроме того, вы указали неверный код. Язык С++ не допускает объявления функций без явного типа возврата.

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


Вы можете встроить рекурсивные функции. Компилятор обычно разворачивает их на определенную глубину VS, у вас даже может быть прагма для этого, и компилятор также может выполнять частичную инкрустацию. Он по существу преобразует его в циклы. Кроме того, как сказал @Evan Teran, компилятор не вынужден встроить функцию, которую вы предлагаете вообще. Это может полностью игнорировать вас и это совершенно правильно.

Проблема с кодом не в том, что встроенная функция. Я уверен, что постоянство или отсутствие аргумента довольно неуместно.

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


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

bigint fac = factorialOf (userInput)

нет возможности компилятору понять это.........

В качестве побочного примечания большинство компиляторов, как правило, игнорируют встроенные строки в отладочных сборках, если специально не указано, что это не делается - упрощает отладку

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

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


Помните, что ключевое слово inline просто отправляет запрос, а не команду компилятору. Компилятор может игнорировать запрос yhis, если определение функции слишком длинное или слишком сложное и скомпилировать функцию как нормальную функцию.

в некоторых случаях, когда встроенные функции могут не работать,

  • Для возвращающих функций, если существует цикл, коммутатор или goto.
  • Для функций, не возвращающих значения, если существует оператор return.
  • Если функция содержит статические переменные.
  • Если в линейных функциях рекурсивны.

следовательно, в С++ встроенные рекурсивные функции могут не работать.

licensed under cc by-sa 3.0 with attribution.