Почему бесконечная рекурсия приводит к отказу seg

Ресурсы вашей системы ограничены. Они ограничены. Даже если в вашей системе больше всего памяти и хранилища на всей Земле, бесконечность НАМНОГО БОЛЬШЕ, чем у вас. Запомни это сейчас.

Единственный способ сделать что-то «бесконечное количество раз» - это «забыть» предыдущую информацию. То есть надо «забыть» то, что было сделано раньше. В противном случае вы должны помнить, что происходило раньше, и для этого требуется хранилище той или иной формы (кеш, память, дисковое пространство, запись на бумаге, ...) - это неизбежно. Если вы храните вещи, у вас есть ограниченное количество свободного места.Напомним, что бесконечность НАМНОГО БОЛЬШЕ, чем то, что есть у вас. Если вы попытаетесь сохранить бесконечное количество информации, у вас закончится место для хранения.

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

По сути, это тот же принцип, что и при переполнении буфера; ОС выделяет фиксированный объем памяти для стека, и когда вы исчерпываете (переполнение стека), вы получаете неопределенное поведение, что в данном контексте означает SIGSEGV.

Основная идея:

int stack[A_LOT];
int rsp=0;

void call(Func_p fn)
    {
    stack[rsp++] = rip;
    rip = fn;
    }

void retn()
    {
    rip = stack[--rsp];
    }

/*recurse*/
for(;;){call(somefunc);}

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

AFAIK: Концы стека защищены адресами, недоступными для процесса. Это предотвращает разрастание стека над выделенными структурами данных и более эффективно, чем явная проверка размера стека, поскольку вам в любом случае необходимо проверить защиту памяти.

Каждый раз, когда вы вызываете f(), вы увеличиваете размер стека - именно там хранится обратный адрес, чтобы программа знала, куда идти, когда f() завершается. Поскольку вы никогда не выходите из f(), стек будет увеличиваться по крайней мере на один обратный адрес при каждом вызове. Как только сегмент стека заполнен, вы получите ошибку segfault. Вы получите аналогичные результаты в каждой ОС.

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

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

Это все еще stackoverflow ;-)

Дело в том, что среда выполнения C не обеспечивает «инструментализацию», как это делают другие управляемые языки (например, Java, Python и т. Д.), Поэтому написание вне пространства, предназначенного для стека, вместо того, чтобы вызывать подробное исключение, просто вызывает ошибку более низкого уровня, которая имеет общее имя «ошибка сегментации».

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

На "низком" уровне стек "поддерживается" с помощью указателя (указателя стека), хранящегося в регистре процессора. Этот регистр указывает на память, поскольку стек - это все-таки память. Когда вы помещаете значения в стек, его "значение" уменьшается (указатель стека перемещается с более высоких адресов на более низкие). При каждом входе в функцию из стека "забирается" некоторое место (локальные переменные); кроме того, на многих архитектурах вызов подпрограммы выталкивает возвращаемое значение в стек (и если процессор не имеет специального регистра-указателя стека, скорее всего, для этой цели используется "обычный" регистр, поскольку стек полезен даже там, где подпрограммы могут вызываться с помощью других механизмов), так что стек как минимум уменьшается на размер указателя (скажем, 4 или 8 байт).

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

Возможно, вам будет интересна эта страница.