Каков порядок величины максимального числа рекурсивных вызовов в С++?

У меня есть рекурсивная функция, которая называет себя очень много раз с определенными входами, что и должно делать. Я знаю, что моя функция не бесконечно зацикливается - она ​​просто доходит до определенного количества вызовов и переполнений. Я хочу знать, если это проблема, если в стек слишком много памяти или просто нормальное ограничение количества вызовов. Очевидно, очень сложно сказать определенное количество вызовов, которое является максимальным, но может ли кто-нибудь дать мне приблизительную оценку порядка величины? Это в тысячах? Сотни? Миллионы?

5 ответов

Это полностью зависит от того, сколько информации вы используете в стеке. Тем не менее, стек по умолчанию для Windows составляет 1 МБ, а стек по умолчанию для Unix - 8 МБ. Просто вызов может включать в себя нажатие нескольких 32-битных регистров и обратного адреса, скажем, чтобы вы могли посмотреть, может быть, 20bytes вызов, который поставил бы максимум около 50k на Windows и 400k в Unix для пустой функции.

Конечно, насколько мне известно, вы можете изменить размер стека.


Итак, как вы уже догадались, проблема в переполнении стека (одноименного). Для каждого вызова требуется создать новый стек стека, вставляя новую информацию в стек; размер стека фиксирован и в конечном итоге заканчивается.

Что задает размер стека? Это свойство компилятора - то есть оно исправлено для двоичного исполняемого файла. В компиляторе Microsoft (используется в VS2010) по умолчанию используется 1 мегабайт, и вы можете переопределить его с помощью "/F" в параметрах компилятора (см. здесь для примера '03, но синтаксис тот же).

Очень сложно понять, сколько звонков соответствует на практике. Размер стека функций определяется его локальными переменными, размером обратного адреса и параметрами (некоторые могут идти в стеке), и многое зависит от архитектуры. Как правило, вы можете предположить, что последние два меньше ста байтов (что валовая оценка). Первое зависит от того, что вы делаете в этой функции. Если вы предполагаете, что в стеке берется, скажем, 256 байт, то с 1M стеком вы получите 4096 вызовов функций перед переполнением - но это не учитывает накладные расходы основной функции и т.д.

Вы можете попытаться уменьшить локальные переменные и накладные расходы параметров, но реальное решение Tail Call Optimization, в котором компилятор выпускает вызов поскольку он вызывает функцию рекурсии. Подробнее об этом можно прочитать в MSVC здесь. Если вы не можете выполнять хвостовые звонки, и вы не можете уменьшить размер стека приемлемо, вы можете посмотреть на увеличение размера стека с параметром "/F" или (предпочтительное решение) на редизайн.


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

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

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

Нет фиксированного предела максимальной глубины рекурсии; вы получите переполнение стека, если ваше общее использование превышает ограничение на стек, налагаемое системой.

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

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

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


Существуют инструменты для измерения использования стека. Они заполняют стек заранее определенным шаблоном байта и затем смотрят на тот адрес, который он изменил. С ними вы можете узнать, насколько близко к пределу вы получаете.

Возможно, один из инструментов valgrind может это сделать.


Одним из вариантов может быть изменение/увеличение стандартного стека. Здесь один из способов http://msdn.microsoft.com/en-us/library/tdkhxaks(v=vs.80).aspx

licensed under cc by-sa 3.0 with attribution.