Java

Как работает рекурсивная функция?

Как я понял - это что то похожее на бесконечный цикл for, который будет выполняться до тех пор, пока условие выхода из основной функции не станет истинным, если мы это условие пропишем. И почему так часто из за него переполняется стек, даже если скажем, мы сортируем массив рекурсией в 10 000 элементов? Ведь данные в стеке на эти 10к элементов по моим подсчетам не так уж много памяти должны занять, особенно, когда у многих нынче по 8-16 гигов оперативы. Или где там этот стек хранится, может, в кеше процессора? Ничего непонятно, разъясните пожалуйста поподробнее, как все это работает.
Алексей Бубнов
Алексей Бубнов
13
нет. это не бесконечный цикл...
переполненние бывает потому, что условие выхода из рекурсии определено неверно...
и ещё потому что в школе на математику клали постоянно, и потому прикинуть не могут масштаб вычислений...

но всё это -- теория..
чё к джаве прикапываться?
ВЛ
Володя Любимцев
79 706
Лучший ответ
Стек используется для вызова подпрограмм. В стек кладётся адрес возврата на который надо вернутся после вызова подпрограммы и передаваемые параметры. Подпрограмма также может использовать стек для своих локальных переменных. Держать локальные переменные в стеке подпрограмма может для поддержки рекурсии и многопоточности.

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

Java создает свой стек на каждый поток. По умолчанию в java размер стека 1M. Иногда его уменьшают до 512K. Накладные расходы на вызов метода это, как минимум, 8 байт на адрес возврата. Локальные переменные java также хранит в стеке. По передаваемым параметрам - Передача параметров в java реализовано только по значению, минимальный размер слота 4 байта.

Например, для передачи четырёх параметров boolean, int, int и массива потребуется
4 + 4 + 4 + 8 = 20 байтов (массив является объектом и, следовательно, передаётся копия его ссылки). Пусть в подпрограмме используется локальных переменных общим размером в 64 байта. Получим, в итоге, 8 + 20 + 64 = 92 байта на один вызов. Для 10000 рекурсивных вызовов это уже будет 920K.
СМ
Станислав Миллер
5 478

Похожие вопросы