Коротко и по делу.
1) Когда рекурсивный поиск без маркировки корректен (терминует и даёт ожидаемый результат)
- если подграф, достижимый от стартовой вершины, не содержит циклов (т.е. это дерево или в общем случае ациклический граф/DAG с учётом направления). Иначе возможна бесконечная рекурсия.
- если цель — просто найти некоторое достижимое состояние и неважно повторное посещение вершин, алгоритм всё равно корректен при отсутствии циклов; в DAG корректность сохраняется, но возможны многократные посещения одной вершины через разные пути.
Итого необходимое/достаточное условие для гарантированной остановки: «нет циклов, достижимых из начальной вершины».
2) Сложность
- При наличии маркировки посещённых вершин (стандартный DFS): время $O(n+m)$, где $n$ — число вершин, $m$ — число рёбер; память (стек/рекурсия) — $O(h)$, где $h$ — глубина обхода, в худшем случае $O(n)$.
- Без маркировки:
- на ацикличном графе с возможными сходимыми путями (DAG) алгоритм терминирует, но может многократно переобрабатывать вершины; в худшем случае время экспоненциально по глубине/числу ветвлений, примерно $O(b^d)$ для факторизации с коэффициентом ветвления $b$ и глубиной $d$.
- если есть циклы, время неограниченно (бесконечная рекурсия).
3) Какие структуры данных и меры нужны, чтобы избежать бесконечной рекурсии и оптимизировать
- Булев массив/множество visited: для каждой вершины пометить «посетили» — основной и самый простой способ. Типы: битсет, булев массив или HashSet. Это гарантирует однократную обработку вершины и даёт сложность $O(n+m)$.
- Цветовая схема (three-color) для ориентированных графов: массив состояний $0$ (white — не посещена), $1$ (gray — в стеке рекурсии), $2$ (black — полностью обработана). Позволяет обнаруживать обратные ребра/циклы при встрече gray и корректно реагировать (например, остановить или пометить цикл).
- Для неориентированного графа достаточно пометки visited; при проверке обратного ребра полезно хранить parent, чтобы не считатъ ребро к родителю циклом.
- Явный стек/итеративный DFS вместо рекурсии: избавляет от системного переполнения стека; можно хранить (вершина, итератор_по_смежным) в стеке.
- Ограничение глубины (depth limit): если поиск должен быть ограничен (iterative deepening), задайте максимальную глубину $d_{max}$ и прекращайте рекурсию по достижении.
- Мемоизация/динамическое программирование на DAG: если задача вычислительная (например, количество путей), кэшируйте результаты для вершины, чтобы избегать перерасчётов.
- Детекция циклов отдельно (алгоритм нахождения сильно связанных компонент, topological sort) — если ваша логика требует работы с DAG, сначала проверьте ацикличность (например, алгоритм Кана или DFS с three-color).
4) Практические советы для реализации
- Всегда используйте visited или colors, если граф может содержать циклы или если пути могут сходиться.
- Для больших графов и риска переполнения стека — перепишите рекурсивный DFS в итеративный с явным стеком.
- Для ориентированных графов для обнаружения циклов применяйте three-color и прерывайте/обрабатывайте при встрече gray.
- Если важна память — используйте битсет для visited; если вершины задаются нецелыми id — HashSet.
- Для сложностных оценок опирайтесь на $n$ и $m$: пометка даёт $O(n+m)$ времени; без пометки — потенциально экспоненциальное время $O(b^d)$.
Кратко: чтобы избежать бесконечной рекурсии на больших/цикличных графах — помечайте посещённые вершины (или используйте three-color/parent), либо замените рекурсию явным стеком/итеративной реализацией, и/или ограничьте глубину поиска.