C++ ограничивает глубину рекурсии?
В Python существует максимальная глубина рекурсии. Кажется, что это - потому что Python является интерпретатором, не компилятором. C++ имеет то же понятие? Или это соединено только с пределом RAM?
6 ответов
Ограничение в C ++ связано с максимальным размером стека. Обычно это на несколько порядков меньше размера ОЗУ, но все же довольно велико. (К счастью, такие большие вещи, как строковое содержимое , обычно хранятся не в самом стеке.)
Предел стека обычно настраивается на уровне ОС. (См. Документацию по встроенной оболочке ulimit , если вы используете Unix.) Значение по умолчанию на этой машине (OSX) - 8 МБ.
[EDIT] Конечно, размер стека сам по себе не совсем помогает, когда дело доходит до определения глубины рекурсии. Чтобы знать это, вы должны вычислить размер записи активации (или записей) рекурсивной функции (также называемой кадром стека). Самый простой способ сделать это (о котором я знаю) - использовать дизассемблер (функция большинства отладчиков) и считывать размер корректировок указателя стека в начале и в конце каждой функции. Что беспорядочно. (Вы можете решить это другими способами - например, вычислить разницу между указателями на переменные в двух вызовах - но они еще более неприятны, особенно для переносимого кода. Считывание значений из разборки проще, IMO.)
C ++ действительно имеет максимальную глубину рекурсии, ограниченную стеком. Однако современные операционные системы могут динамически расширять стек пользовательского пространства по мере его заполнения, ограничивая глубину рекурсии только пространством памяти и фрагментацией памяти.
Я считаю, что предел - это размер стека, доступного на платформе. Из того, что я читал, в Linux по умолчанию 8K 8MB, но современные ядра могут динамически регулировать размер стека.
Нет, C ++ не имеет явной глубины рекурсии. Если максимальный размер стека превышен (который по умолчанию составляет 1 МБ в Windows), ваша программа на C ++ переполнит ваш стек, и выполнение будет прекращено.
В стандартах C или C ++ нет отслеживания глубины рекурсии или ограничений. Во время выполнения глубина ограничена размером стека.
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 не оптимизирует хвостовую рекурсию (но stackless Python оптимизирует), а C++ не требует оптимизации хвостовой рекурсии, но я полагаю, что gcc оптимизирует хвостовую рекурсию. JVM не оптимизирует хвостовую рекурсию, хотя язык Scala делает это в некоторых общих документированных случаях. Scheme и Lisp (и, вероятно, другие функциональные языки) требуют, чтобы хвостовая рекурсия была оптимизирована.