Ограниченная рекурсия в C?

Question

Я запустил эту программу, и она вывела

...

65088
65089
65090

и затем оно остановилось. Windows 7 сказала, что a.exe перестал работать. Вот код:

#include <stdio.h>

void go(void);

main()
{
    go();
}

void go(void)
{
    static int i = 0;
    printf("%d\n", i++);
    go();
}

Я думаю, что эта программа должна бесконечно печатать числа из-за рекурсии, но она останавливается на 65090! Код на C компилируется с помощью gcc. Есть идеи?

Answer 1

В какой-то момент вы переполните стек, потому что каждый вызов go() должен помещать адрес возврата в стек, даже если вы не передаете аргументы в вызов функции.Таким образом, каждый вызов go() занимает блок размером с указатель в стеке для этого обратного адреса.Поскольку размер стека ограничен, это означает, что в какой-то момент вам не хватит места.Язык C не указывает, что оптимизация хвостового вызова должна проводиться при подобных обстоятельствах, хотя некоторые компиляторы (например, gcc) предлагают эту опцию с помощью переключателей оптимизации.Но это будет что-то, что зависит от компилятора и не зависит от спецификации языка.

Answer 2

Останавливается, потому что переполняет стек.После переполнения стека результаты не определены.

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

Прежде всего, это не C, который ограничивает рекурсию .Это ваша операционная система!

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

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

В Windows, если вам нужно увеличить размер стека, вы можете попробуйте это .

Answer 7

Я думаю, вам не хватает места в вашем стеке.Вашей программе разрешен только определенный объем памяти (который, вероятно, может изменить ваша среда разработки), и поскольку go () вызывается внутри себя, одновременно существует 65000 копий вызова функции.

Answer 8

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

Answer 9

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