Что использовать в итеративном алгоритме вместо стека вызовов?

Что проверяют

Понимаете ли вы, что рекурсия это неявный стек кадров, и умеете ли перенести его в явную структуру. Вопрос обычно всплывает после падения с StackOverflowError на глубоких данных, и ждут не термина, а плана переписывания.

Как отвечать

Главное: вместо стека вызовов берут собственную структуру в куче. Для обхода в глубину это стек, для обхода в ширину очередь, обе роли закрывает ArrayDeque.

Deque<Node> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
    Node node = stack.pop();
    visit(node);
    List<Node> children = node.children();
    for (int i = children.size() - 1; i >= 0; i--) {
        stack.push(children.get(i));
    }
}

Дальше важные детали:

• порядок: дети кладутся в обратном порядке, иначе обход получится зеркальным к рекурсивному;
• на графе нужен набор посещённых вершин, иначе цикл в данных даёт бесконечную работу;
• если после возврата из рекурсии ещё выполняется код, одного узла в стеке мало. Кладите свой кадр: объект или запись с полями «узел», «индекс следующего потомка», «накопленный результат». Это ровно то, что хранил стек вызовов;
• хвостовая рекурсия разворачивается в цикл руками, рассчитывать на оптимизацию от JVM нельзя, она её не делает.

Полезно добавить про границы: глубина теперь упирается в кучу, а не в размер стека потока. Это на порядки больше, но не бесконечность.

Где спотыкаются

Берут java.util.Stack. Он синхронизирован, наследует Vector и обходится итератором в порядке вставки, а не в порядке снятия. Для этой роли давно берут ArrayDeque.

Второе: забывают про посещённые вершины и про обратный порядок вставки. Получают либо другой порядок обхода, чем у рекурсивной версии, либо зацикливание на графе, где есть цикл.

Третье: считают, что переписывание само по себе ускоряет. Выигрыш тут в устойчивости к глубине: вызовы в JVM дёшевы и хорошо оптимизируются, а явная структура добавляет расходы на объекты. Переписывают ради предсказуемости, а не ради микросекунд.