Подтвердить что ты не робот

Бесконечная рекурсия в C

Учитывая программу C с бесконечной рекурсией:

int main() {

    main();

    return 0;
}

Почему это приведет к переполнению стека. Я знаю, что это приводит к поведению undefined в С++ из следующего потока Является ли эта бесконечная рекурсия UB? (и как сторона node нельзя вызвать main() в С++). Однако valgrind говорит мне, что это приводит к переполнению стека:

Qaru in thread 1: can't grow stack to 0x7fe801ff8

а затем, наконец, программа заканчивается из-за ошибки сегментации:

==2907== Process terminating with default action of signal 11 (SIGSEGV)
==2907==  Access not within mapped region at address 0x7FE801FF0

Это также поведение undefined в C, или это должно привести к переполнению стека, а затем почему это приводит к переполнению стека?

изменить

1 Я хотел бы знать, что бесконечная рекурсия разрешена в C?
2 Если это приведет к переполнению стека? (был достаточно дан ответ)

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

Из этого следует, что после того, как сегмент стека исчерпан, эту функцию нельзя назвать aynmore, и к ОС добавляется исключение. Теперь могут случиться две вещи. Либо ОС пересылает исключение обратно в ваше приложение, которое вы увидите как переполнение стека. Или ОС может попытаться выделить дополнительное пространство для segemnt стека, до определенного предела, после чего приложение увидит переполнение стека.

Итак, этот код (я переименовал его в infin_recursion(), поскольку main() не может быть вызван)...

int inifinite_recursion(void)
{
    inifinite_recursion();
    return 0;
}

... выглядит так:

_inifinite_recursion:
    push    ebp                    ; 4 bytes on the stack
    mov ebp, esp

    call    _inifinite_recursion   ; another 4 bytes on the stack
    mov eax, 0                 ; this will never be executed.

    pop ebp
    ret

UPDATE

Что касается стандарта C99 для определения рекурсии, то лучшее, что я нашел до сих пор, содержится в разделе 6.5.2.2. Пункт 11:

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

Конечно, это не отвечает, определено ли, что происходит при переполнении стека. Однако, по крайней мере, это позволяет main называться рекурсивно, тогда как это явно запрещено в С++ (раздел 3.6.1, абзац 3 и параграф 5.2.2 параграф 9).

Ответ 2

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

Ответ 3

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

void iteration_2 (int x) {
    /* ... */
}

void iteration_1 (int x) {
    if (x > 0) return;
    iteration_2(x + 1);
}

void iteration_0 (int x) {
    if (x > 0) return;
    iteration_1(x + 1);
}

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

void iteration (int x) {
    if (x > 0) return;
    iteration(x + 1);
}

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

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

int iteration () {
    return iteration();
}

При компиляции с gcc -O0 он становится:

iteration:
.LFB2:
        pushq   %rbp
.LCFI0:
        movq    %rsp, %rbp
.LCFI1:
        movl    $0, %eax
        call    iteration
        leave
        ret

Но при компиляции с gcc -O2 рекурсивный вызов удаляется:

iteration:
.LFB2:
        .p2align 4,,7
.L3:
        jmp     .L3

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

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

Стандарт не говорит о "бесконечной рекурсии" в каких-либо конкретных терминах. Я собрал вместе то, что, по моему мнению, относится к вашему вопросу.

  • Разрешается вызов функции рекурсивно (C.11 и раздел; 6.5.2.2 и пункт 11)

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

  • Рекурсивная запись в оператор создает новые экземпляры локальных переменных (C.11 и sect; 6.2.4 и para; 5,6,7)

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

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

Для такого объекта, который имеет тип массива переменной длины, его время жизни продолжается от объявление объекта до выполнения программы оставляет область действия декларация. Если область вводится рекурсивно, создается новый экземпляр объекта каждый раз.

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

Ответ 4

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

Размер стека часто ограничен и определяется до выполнения (например, вашей операционной системой).

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

Ответ 5

Даже если функция не использует пространство стека для локальных переменных или передачи аргументов, все равно необходимо сохранить обратный адрес и (возможно) базовый указатель кадра (с gcc, это можно отключить с помощью -fomit-frame-pointer).

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

Ответ 6

Адресация вопросов 1:

Я хотел бы знать, что бесконечная рекурсия разрешена в C?

Эта статья Compilers and Termination Revisited John Regehr - это ответ на вопрос, разрешает ли C standard бесконечную рекурсию или нет, и после расчёта по стандарту для меня не слишком удивительно, что выводы заключаются в том, что они неоднозначны. Основная цель статьи - бесконечные циклы и поддерживается ли она стандартом различных языков (включая C и C++) для выполнения без прерывания. Насколько я могу судить, дискуссия применима и к бесконечной рекурсии, конечно, предполагая, что мы можем избежать.

В отличие от C++, который гласит в разделе 1.10 Multi-threaded executions and data races paragraph 24:

The implementation may assume that any thread will eventually do one of the
following:
  — terminate,
  [...]

Что, по-видимому, исключает бесконечную рекурсию в C++. draft C99 standard говорит в разделе 6.5.2.2 Function calls paragraph 11:

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

который не ограничивает рекурсию и говорит об этом в разделе 5.1.2.3 Program execution paragraph 5:

The least requirements on a conforming implementation are:
— At sequence points, volatile objects are stable in the sense that previous 
  accesses are complete and subsequent accesses have not yet occurred.
— At program termination, all data written into files shall be identical to the
  result that execution of the program according to the abstract semantics would
  have  produced.
— The input and output dynamics of interactive devices shall take place as
  specified in 7.19.3. The intent of these requirements is that unbuffered or     
  line-buffered output appear as soon as possible, to ensure that prompting
  messages actually appear prior to a program waiting for input.

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

Если речь идет о завершении программы, запущенной на абстрактной машине, то она неэффективно встречается, потому что наша программа не заканчивается. Если речь идет о завершении фактической программы, сгенерированной компилятором, то реализация C ошибочна, потому что данные, записанные в файлы (stdout - это файл), отличаются от данных, написанных абстрактной машиной. (Это чтение связано с Хансом Бёмом, я не смог поддразнить эту тонкость из стандарта.)

Итак, у вас есть это: поставщики компилятора читают стандартный один путь, а другие (например, я) читают его другим способом. Его довольно ясно, что стандарт ошибочен: он должен, подобно С++ или Java, быть однозначным в отношении того, разрешено ли это поведение.

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

Ответ 7

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

Ответ 8

Важно понять, как выглядит вызывающий стек функций в C:

function stack

Ответ 9

Разрешена ли бесконечная рекурсия в C? Простой ответ - да. Компилятор позволит вам бесконечно вызывать функцию, пока не закончится пространство стека; это не помешает вам сделать это.

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

Возможно ли поддельная бесконечная рекурсия? Да. Можно создать функцию, которая называет себя 1000 раз, а затем позволяет себе выйти из 1000 вызовов функций, так что стек имеет только исходный вызов функции в стеке... а затем повторить весь процесс заново в бесконечный цикл. Однако я не считаю эту реальную бесконечную рекурсию.

Ответ 10

Бесконечная рекурсия разрешена в C. Во время компиляции это разрешит, но при этом вы можете получить ошибку времени выполнения.

Ответ 11

Это разрешено в c, так как в стандарте говорится →

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

В 6.5.2.2 → 11

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

Ответ 12

Причина, когда стек ограничен, и всякий раз, когда вы вызываете функцию, она сохраняет вызываемого абонента (путем нажатия указателя базы на стек и копирования текущего указателя стека в качестве нового значения базового указателя), поэтому потребление стека будет переполняться с бесконечным количеством вызовов. См. Соглашение о вызове и то, как здесь реагирует стек (http://www.csee.umbc.edu/~chang/cs313.s02/stack.shtml)

Ответ 13

Я просто посмотрел на копию недавнего проекта c стандартов doc, и ни одна из ссылок рекурсии не говорит о бесконечной рекурсии.

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