Бесконечные рекурсивные вызовы должны вызывать переполнение стека в этом случае?

Question

Я недавно думал об этом случае переполнения стека:

int f()  
{  
    return f();  
}  

int main(void)  
{  
    f();  
    return 0;  
}

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

int f()
{
    int x = f();
    return x;
}

int main(void)
{
    f();
    return 0;
}

Конечно, я что-то упустил, я был бы признателен, если бы кто-то объяснил этомне.Привет

Answer 1

Оказывается, что в некоторых компиляторах с правильными флагами оптимизации это не вызовет переполнения стека! На самом деле я пытался скомпилировать вашу программу в g++. При оптимизации по умолчанию это вызывает переполнение стека, но на уровне оптимизации -O3 оно просто входит в бесконечный цикл.

Причина различия между бесконечной рекурсией и бесконечными циклами связана с тем, что компилятор по умолчанию реализует эти конструкции. Циклы исторически были реализованы с использованием инструкций ветвления, которые сообщают процессору о необходимости выполнения в другой части программы. Все эти инструкции выполняют переход к другому счетчику программ, который просто изменяет содержимое регистра. С другой стороны, вызовы функций реализуются путем добавления новой записи активации в стек для кодирования аргументов, адреса возврата и т. Д., Чтобы при возврате функции она знала, куда возвращаться.

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

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

Answer 2

Вы ничего не упускаете. Скомпилируйте программу, используя gcc -O2, и переполнение стека отсутствует.

Answer 3

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

Answer 4

C не требуется для устранения оконечных вызовов.(Схема обязательна для выполнения TCO .)

Answer 5

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

Answer 6

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