Аварийное завершение из-за переполнения стека
Недавно я написал вступительный тест в аспирантуру несколько дней назад, и в нем появился следующий вопрос.
Когда приведенная ниже функция вызывается с любым положительным целым числом в качестве аргумента, завершается ли она? И печатает ли что-нибудь?
void convert (int n)
{
if (n < 0)
printf ("%d", n);
else
{
convert (n/2);
printf ("%d", n%2);
}
}
По моему мнению, ничего не будет напечатано, поскольку элемент управления никогда не попадает внутрь оператора if, а также поскольку оператор printf помещается после вызова функции в блоке else. Значение n никогда не становится ниже 0, и функция вызывает себя снова и снова, пока стек не переполнится. Мой вопрос заключается в том, будет ли код аварийно завершен из-за переполнения стека?
...Я предположил, что вас уволили по странной причине, связанной с публикацией на этом сайте.
Ответы 3
Код не завершится положительным целочисленным аргументом, поскольку базовое условие n < 0 никогда не будет выполнено.
Рекурсивный вызов convert вызывает его с аргументом n / 2, который, как целочисленное деление, неизбежно даст достигать ноль, но не меньше него.
Например, с аргументом 10:
call convert(10)
10 < 0 is false; enter the else branch
call convert(10 / 2)
5 < 0 is false; enter the else branch
call convert(5 / 2)
2 < 0 is false; enter the else branch
call convert(2 / 2)
1 < 0 is false; enter the else branch
call convert(1 / 2)
0 < 0 is false; enter the else branch
call convert(0 / 2)
0 < 0 is false; enter the else branch
call convert(0 / 2)
0 < 0 is false; enter the else branch
call convert(0 / 2)
0 < 0 is false; enter the else branch
Он никогда не войдет в базовый случай.
Код завершится с переполнением стека или нет, в зависимости от вывода компилятора.
Выхода не будет. потому что n никогда не будет меньше, чем 0.
С наивным компилятором, который делает компилирует рекурсию без оптимизации, вы получите переполнение стека в большинстве (если не во всех) реализациях.
Да, если оптимизатор вашего компилятора не сделает что-то необычное, эта программа аварийно завершится из-за переполнения стека.
Причина в том, что функция convert() рекурсивно вызывается бесконечно много раз. Вы это уже знали, но дело вот в чем: каждая рекурсивная запись в convert() помещает в стек новый фрейм. Каждый кадр включает в себя адрес возврата к предыдущему кадру и локальное значение n.
У компиляторов есть оптимизаторы, но оптимизатор должен быть необычным, чтобы интуитивно понять, что эта функция (а) не имеет побочных эффектов и (б) не возвращает никакого значения. Поэтому маловероятно, что оптимизатор убережет этот код от аварийного завершения.
Я считаю, что вы правильно ответили на этот вопрос.
Тем временем комментатор напомнил нам об особом случае — хвостовой рекурсии. Если бы рекурсивный вызов завершил функцию, как, например, return convert(n/2);, то компилятор мог бы иметь повторно использованный один кадр стека для всех рекурсивных вызовов. Причина: к моменту рекурсивного вызова текущий вызов уже не требует своего хранения; объект n может быть безопасно перезаписан новым n для рекурсивного вызова; необходимо будет сохранить только обратный адрес исходному вызывающему абоненту. Если применить хвостовую рекурсию, стек не будет расти и, следовательно, программа не завершится ни аварийно, ни каким-либо иным образом. Однако хвостовая рекурсия здесь не применяется.
Код может быть оптимизирован, поэтому он не будет потреблять стек. Но в остальном вы правы.