Выбор ответа Middle Задачи на Java обновлено
Рекурсивный DFS на большом графе
Вопрос
Рекурсивный DFS по цепочке из 10⁶ вершин падает. Что вероятнее всего произошло?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: StackOverflowError: глубина рекурсии больше стека потока. Каждый рекурсивный вызов занимает фрейм в стеке потока, а стек по умолчанию порядка мегабайта: миллион уровней не помещается.
Варианты ответа
- StackOverflowError: глубина рекурсии больше стека потокаправильный ответ
- OutOfMemoryError: граф из 10⁶ вершин не помещается в кучу
- Бесконечный цикл обхода из-за отсутствия массива visited
- Превышен лимит времени из-за медленных вызовов методов
Разбор
Каждый рекурсивный вызов занимает фрейм в стеке потока, а стек по умолчанию порядка мегабайта: миллион уровней не помещается. Граф на 10⁶ вершин в куче занимает десятки мегабайт, это не проблема. Без visited на цепочке нет циклов. Решение: итеративный обход с явным стеком или поток с увеличенным стеком.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.