Рекурсивный обход цепочки из 100 000 элементов падает со StackOverflowError — перепишите его без рекурсии
Проверила команда Сопровод · Обновлено
Короткий ответ
Каждый рекурсивный вызов кладет кадр в стек потока, а размер стека на Linux x64 по умолчанию 1 МБ: на 100 000 вызовах он кончается. Хвостовую рекурсию Java не оптимизирует, поэтому перепишите обход циклом: идите по ссылке previous, пока она не станет null, и считайте шаги. Дополнительная память выйдет O(1). Для дерева заведите явный стек на ArrayDeque.
Почему этот вопрос задают
Вопрос связывает устройство JVM с повседневным кодом. По ответу видно, понимаете ли вы, что такое кадр стека, почему флаг -Xss не решает проблему и умеете ли превращать рекурсию в цикл.
Условие задачи
Онлайн-редактор сохраняет версию документа после каждой правки, и каждая версия хранит ссылку на предыдущую: record Version(String id, Version previous). У регламента службы поддержки, который правят каждый день, за три года набралось 100 000 версий. Их число считал рекурсивный метод depth(v): он возвращает 1, если предыдущей версии нет, иначе 1 + depth(v.previous()). На этом регламенте метод падает со StackOverflowError. Перепишите подсчет без рекурсии, для этой цепочки он должен вернуть 100000.
Как подойти к решению
- Объясните, откуда ошибка: каждый вызов
depthдобавляет кадр в стек потока - Замените рекурсию циклом, который идет по ссылке
previousдоnull - Держите в цикле только текущую версию и счетчик шагов
- Проверьте крайние случаи: первая версия без предыдущей дает 1,
nullна входе дает 0
Решение
Цикл не создает новых кадров, поэтому длина цепочки ограничена только кучей: время O(n), дополнительная память O(1). Для null метод вернет 0, это совпадает со смыслом «версий нет». Цепочку для проверки строит цикл в main: каждая новая версия ссылается на предыдущую.
public class Main {
public static void main(String[] args) {
Version last = new Version("v1", null);
for (int i = 2; i <= 100_000; i++) last = new Version("v" + i, last);
System.out.println(chainLength(last));
}
static int chainLength(Version version) {
int length = 0;
for (Version v = version; v != null; v = v.previous()) length++;
return length;
}
}
record Version(String id, Version previous) {}100000
Что спросят следом
Как без рекурсии обойти дерево версий, где от одной версии отходит несколько веток?
Что делать, если из-за ошибки в данных цепочка замкнулась в кольцо?
Почему Java не оптимизирует хвостовую рекурсию?
Доступно по подписке
Ответы на эти вопросы
Частые ошибки
«Увеличу стек через
-Xss, и все заработает»Это только отодвигает предел. На JDK 21 под Linux x64 со стеком по умолчанию 1 МБ рекурсия на 100 000 падает, с
-Xss8mпроходит и снова падает на миллионе версий«Распечатаю
last, чтобы посмотреть цепочку в отладке»Сгенерированный
toString()записи рекурсивно печатает всю цепочку и сам падает соStackOverflowErrorуже на нескольких тысячах версий.hashCode()иequals()у такой записи тоже рекурсивны«Рекурсия здесь естественнее, цикл — преждевременная оптимизация»
Для связного списка цикл читается так же просто, а на длинной цепочке рекурсия упадет. Рекурсию оставьте для структур с небольшой известной глубиной, например для сбалансированного дерева
«Соберу цепочку в
ArrayListи возьмуsize()»Рекурсии тут нет, но вы потратите O(n) памяти на список, который нужен лишь для счета. Счетчик в цикле дает тот же ответ при O(1) памяти
Сигналы для интервьюера
Сильный ответ
Связывает ошибку с размером стека потока, сравнивает память рекурсивного и итеративного решений и объясняет выбор
Тревожный сигнал
Предлагает обернуть вызов в try и при StackOverflowError вернуть запасное значение вместо исправления обхода
Красный флаг
Путает StackOverflowError с OutOfMemoryError и всерьез предлагает поднять размер кучи через флаг -Xmx
Как еще могут спросить
- Что такое
StackOverflowErrorи когда он возникает? - Как переписать рекурсию через цикл в Java?
- Почему глубокая рекурсия падает в Java и как это исправить?
- Что делать, если рекурсивный метод падает на больших данных?











