В чем разница между рекурсивным и итеративным подходом к обходу в глубину (DFS), и когда стоит выбирать один вместо другого?

Обход в глубину (DFS) — это стратегия обхода графа или дерева, при которой мы идём как можно глубже по одной ветке, прежде чем вернуться назад. Реализовать эту стратегию можно двумя способами: через рекурсию или через явный стек. Оба варианта дают одинаковый порядок обхода, но различаются по потреблению памяти и удобству использования.

Рекурсивный DFS

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

function dfsRecursive(graph, node, visited = new Set()) {
  if (visited.has(node)) return;
  visited.add(node);
  console.log(node);
  for (const neighbor of graph[node]) {
    dfsRecursive(graph, neighbor, visited);
  }
}

Главный минус — ограничение глубины стека вызовов. В JavaScript, Python и Java глубина рекурсии обычно ограничена несколькими тысячами вызовов. На графе с миллионом вершин в цепочке программа упадёт с ошибкой переполнения стека.

Итеративный DFS

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

function dfsIterative(graph, start) {
  const stack = [start];
  const visited = new Set();
  while (stack.length) {
    const node = stack.pop();
    if (visited.has(node)) continue;
    visited.add(node);
    console.log(node);
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) stack.push(neighbor);
    }
  }
}

Обратите внимание: чтобы получить тот же порядок обхода, что и в рекурсии, соседей иногда нужно добавлять в стек в обратном порядке. Это частая деталь на собеседованиях.

Когда что выбирать

• Рекурсия — когда граф неглубокий, важна читаемость и краткость кода.
• Итерация — когда глубина может быть большой, важна устойчивость к переполнению стека или нужен контроль над порядком обхода.
• В продакшене для обхода больших графов (соцсети, файловые системы, компиляторы) чаще используют итеративный вариант.

Итог: рекурсивный DFS удобен для учебных задач и небольших структур, а итеративный — надёжный выбор для реальных систем, где глубина данных непредсказуема.