Выбор ответа Middle Графы: BFS и DFS обновлено
Рекурсивный DFS на большой сетке
Вопрос
Рекурсивный DFS заливает остров на сетке 1000 × 1000, состоящей целиком из суши. Что может случиться в JS?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: RangeError: переполнение стека, глубина до миллиона. Глубина DFS может достигать числа клеток.
Варианты ответа
- Ничего: рекурсия в JS ограничена только объёмом кучи
- Обход станет O(n²) из-за повторных заходов в клетки
RangeError: переполнение стека, глубина до миллионаправильный ответ- Сработает хвостовая оптимизация, и стек не вырастет
Разбор
Глубина DFS может достигать числа клеток. Стек вызовов в V8 рассчитан примерно на десятки тысяч кадров (точное число зависит от размера кадра и настроек), миллион не влезет. Решение: итеративный DFS со своим стеком или BFS.
- Рекурсия ограничена размером стека.
- Сложность остаётся O(R · C), проблема в памяти стека.
- В V8 нет хвостовой оптимизации (поддерживает только Safari), и этот DFS не хвостовой.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.