Ограничивает ли рекурсия глубину С++?

Ответ 1

Предел в С++ связан с максимальным размером стека. Это обычно меньше, чем размер ОЗУ на несколько порядков, но все еще довольно большой. (К счастью, большие вещи, такие как содержимое строки, обычно хранятся не в самом стеке.)

Предел стека обычно настраивается на уровне ОС. (См. Документацию для встроенной оболочки ulimit, если вы находитесь в Unix.) Значение по умолчанию на этом компьютере (OSX) составляет 8 МБ.

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

Ответ 2

Нет, С++ не имеет явной глубины рекурсии. Если максимальный размер стека превышен (по умолчанию он равен 1 МБ в Windows), ваша программа на С++ переполнит ваш стек, и выполнение будет прекращено.

Ответ 3

Нет следов или ограничений глубины рекурсии в стандартах C или С++. Во время выполнения глубина ограничена тем, насколько большой стек может расти.

Ответ 4

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

Ответ 5

Я считаю, что ограничение - это размер стека, доступного на платформе. Из того, что я прочитал, он по умолчанию 8K 8 МБ в Linux, но современные ядра могут динамически изменять размер стека.

Ответ 6

Python имеет настраиваемый предел для рекурсивных вызовов, а С++ ограничен размером стека.

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

int fact(int n, int accum=1){
  if (n==0) return accum;
  else return fact(n-1,n*accum); //tail recursion here.
}

Python не оптимизирует хвостовую рекурсию (но stackless Python), а С++ не требует оптимизации хвостовой рекурсии, но я считаю, что gcc оптимизирует хвостовую рекурсию. JVM не оптимизирует хвостовую рекурсию, хотя язык Scala используется в некоторых распространенных документальных случаях. Схема и Lisp (и, возможно, другие функциональные языки) требуют оптимизации хвостовой рекурсии.