Выбор ответа Middle Задачи на Kotlin обновлено
Глубокая рекурсия на JVM
Вопрос
DFS рекурсией по графу-цепочке из 10^5 вершин падает с StackOverflowError. Какое решение самое надёжное?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Переписать обход итеративно с явным стеком. Каждый рекурсивный вызов занимает кадр стека потока, а стек JVM по умолчанию около 1 МБ.
Варианты ответа
- Увеличить
timeLimitMsзадачи - Пометить функцию
inline - Переписать обход итеративно с явным стекомправильный ответ
- Использовать
HashMapвместо массива смежности
Разбор
Каждый рекурсивный вызов занимает кадр стека потока, а стек JVM по умолчанию около 1 МБ. Итеративный DFS с IntArray или ArrayDeque в роли стека не зависит от глубины. Запуск в потоке с большим стеком тоже работает, но зависит от настроек проверяющей системы. Время, inline (рекурсивную функцию нельзя сделать inline) и структура хранения графа проблему не решают.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.