Аварийное завершение из-за переполнения стека

Question

Я недавно написал свой тест для поступления в аспирантуру несколько дней назад, и в тесте появился следующий вопрос:
Когда приведенная ниже функция вызывается с любым положительным целым числом в качестве аргумента, он заканчивается?Также печатает ли он что-нибудь?

void convert (int n) 
{
  if (n < 0)
    printf ("%d", n);
  else 
  {
    convert (n/2);
    printf ("%d", n%2);
  }
}

По моему мнению, ничего не будет напечатано, поскольку элемент управления никогда не будет достигнут внутри оператора if, а также, поскольку оператор printf помещается после вызова функции в блоке else.Значение n никогда не достигает значения ниже 0, и функция вызывает себя снова и снова, пока стек не переполнится.Мой вопрос заключается в том, будет ли код аварийно завершен из-за переполнения стека?

Answer 1

Код будет заканчиваться стекопотоком или не зависит от выходных данных компилятора.

Вывод не будет.поскольку n никогда не будет меньше 0.

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

Answer 2

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

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

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

Я полагаю, что вы правильно ответили на этот вопрос.

Тем временем комментатор напомнил нам об особом случае, tailрекурсии.Если рекурсивный вызов завершил функцию, как, например, return convert(n/2);, то компилятор мог бы повторно использовать один кадр стека для всех рекурсивных вызовов.Причина: к тому времени, когда происходит рекурсивный вызов, текущий вызов больше не требует его хранения;объект n может быть безопасно перезаписан новым n для рекурсивного вызова;необходимо сохранить только обратный адрес исходному абоненту.Если применяется хвостовая рекурсия, стек не будет расти и, следовательно, программа не будет завершена, ни ненормально, ни иначе.Однако рекурсия хвоста здесь не применима.

Answer 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

Он никогда не войдет в базовый регистр.