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

Question

В Python максимальная глубина рекурсии. Кажется, это потому, что Python является интерпретатором, а не компилятором. C ++ имеет ту же концепцию? Или это связано только с лимитом оперативной памяти?

Answer 1

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

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

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

Answer 2

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

Answer 3

В стандартах C или C ++ нет отслеживания или ограничения глубины рекурсии. Во время выполнения глубина ограничена размером стека.

Answer 4

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

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

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

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

Answer 5

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

Answer 6

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