0Pricing
SQL Interview Prep · Урок

Предотвращение бесконечной рекурсии

Обнаружение циклов, ограничение глубины и защитный механизм рекурсии, который проверяют на каждом собеседовании.

«Предотвращение бесконечной рекурсии» — бесплатный урок SQL Interview Prep на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения SQL Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс SQL Interview Prep содержит 4 уроков всего.

Вопрос, который скрывается за вопросом

После написания рекурсивного CTE опытный интервьюер спросит: «Что произойдёт, если в данных есть цикл?» Это проверяет, понимаете ли Вы, что рекурсия может выполняться бесконечно, и знаете ли, как этого не допустить.

Цикл возникает, когда иерархия замыкается сама на себе: A подчиняется B, а B — A. Наивная рекурсивная часть будет бесконечно переходить от одного к другому.

Как образуется цикл

Деревья должны быть ацикличными, но реальные данные бывают неаккуратными. Из-за ошибочного обновления сотрудник может стать собственным (косвенным) руководителем. Граф, например «пользователи, которые подписаны на пользователей», по своей природе может содержать циклы.

Когда рекурсивная часть снова встречает уже посещённый узел, она создаёт его повторно, из-за чего вновь запускается обработка его дочерних узлов, и цикл никогда не опустошается. Рекурсия останавливается только тогда, когда некоторый шаг возвращает ноль строк; цикл гарантирует, что строки будут возвращаться всегда.

Защита 1: ограничение глубины

Самая простая мера безопасности — счётчик глубины с верхним пределом в рекурсивной части. Даже если существует цикл, рекурсия остановится при достижении этого предела.

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

WITH RECURSIVE org AS (
    SELECT id, name, manager_id, 1 AS depth
    FROM employees WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, e.manager_id, o.depth + 1
    FROM employees e JOIN org o ON e.manager_id = o.id
    WHERE o.depth < 50
)
SELECT * FROM org;

Защита 2: путь посещённых узлов

Точная защита отслеживает путь посещённых узлов и не позволяет снова войти в узел, который уже находится в этом пути. Накапливайте идентификаторы в строке (или массиве) и перед рекурсивным переходом проверяйте наличие узла.

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

WITH RECURSIVE org AS (
    SELECT id, name, manager_id,
           CAST(',' || id || ',' AS VARCHAR(2000)) AS path
    FROM employees WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, e.manager_id,
           o.path || e.id || ','
    FROM employees e JOIN org o ON e.manager_id = o.id
    WHERE o.path NOT LIKE '%,' || e.id || ',%'
)
SELECT id, name, path FROM org;

Почему проверка пути работает

Условие path NOT LIKE '%,' || e.id || ',%' означает: «переходить по этой связи можно только в том случае, если идентификатора дочернего узла ещё нет в пути». Запятые служат разделителями, поэтому идентификатор 1 не ошибочно совпадёт с частью идентификатора 15.

Если цикл приведёт к повторному посещению узла, WHERE отфильтрует эту строку, рекурсивная часть в итоге не вернёт ничего, и рекурсия корректно завершится.

Защита 3: встроенное предложение CYCLE

Современный Postgres (14 и выше) и стандарт SQL предлагают встроенное предложение CYCLE, которое автоматически проверяет путь и отмечает циклы. Это самый аккуратный вариант, если система его поддерживает.

WITH RECURSIVE org AS (
    SELECT id, name, manager_id FROM employees WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, e.manager_id
    FROM employees e JOIN org o ON e.manager_id = o.id
)
CYCLE id SET is_cycle USING cycle_path
SELECT id, name, is_cycle FROM org;

MAXRECURSION в SQL Server

SQL Server по умолчанию ограничивает рекурсию 100 уровнями. Если цикл (или глубокое дерево) превышает этот предел, запрос завершается с ошибкой, а не выполняется бесконечно — это встроенная мера безопасности.

Предел можно увеличить или снять с помощью OPTION (MAXRECURSION n), где 0 означает отсутствие ограничения. Но снятие предела без проверки пути вновь создаёт риск бесконечного цикла в циклических данных.

-- Cap recursion at 200 levels in SQL Server
SELECT * FROM org
OPTION (MAXRECURSION 200);

Обнаружение и предотвращение циклов

На собеседовании могут различать две цели:

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

Знание обоих подходов и понимание, когда уместен каждый из них, отличает специалиста старшего уровня.

Вопросы производительности

Рекурсия может быть затратной даже без циклов. Вот советы, которые интервьюеры любят слышать:

  • Создайте индекс для столбца соединения (например, manager_id), чтобы соединение на каждой итерации выполнялось быстро.
  • Фильтруйте данные уже в начальной части, чтобы начать только с нужного поддерева, а не со всей таблицы.
  • Избегайте SELECT * — переносите только столбцы, необходимые рекурсии, а также depth/path.

Безопасный шаблон

Объедините защиты в шаблон, который можно воспроизвести под давлением: столбец глубины как резервная мера, проверка пути как точная защита. Даже если для чистых данных одна из мер избыточна, демонстрация обеих говорит о строгости подхода.

WITH RECURSIVE walk AS (
    SELECT id, parent_id, 1 AS depth,
           CAST(',' || id || ',' AS VARCHAR(4000)) AS path
    FROM nodes WHERE parent_id IS NULL
    UNION ALL
    SELECT n.id, n.parent_id, w.depth + 1,
           w.path || n.id || ','
    FROM nodes n JOIN walk w ON n.parent_id = w.id
    WHERE w.depth < 100
      AND w.path NOT LIKE '%,' || n.id || ',%'
)
SELECT id, depth FROM walk;

Распространённые ошибки на собеседовании

Последние ловушки, которых следует избегать:

  • Удаление MAXRECURSION в SQL Server без другой защиты — это вновь создаёт риск бесконечного цикла.
  • Слишком короткий строковый столбец пути, из-за чего происходит усечение и защита незаметно перестаёт работать.
  • Сопоставление идентификаторов без запятых-разделителей, из-за чего идентификатор 1 ошибочно совпадает с частью идентификатора 21.
  • Предположение, что данные ацикличны, только потому, что «так должно быть», — всегда проверяйте это.

Быстрая проверка

Выберите защиту, которая точно останавливает циклы, не ограничивая допустимую глубину.

Итоги

Каждый ответ с рекурсивным CTE должен учитывать безопасность:

  • Из-за циклов рекурсивная часть никогда не возвращает пустой результат, поэтому рекурсия не останавливается.
  • Ограничение глубины = быстрая резервная мера; проверка пути посещённых узлов = точное предотвращение циклов; предложение CYCLE = встроенное обнаружение в современных системах.
  • MAXRECURSION 100 в SQL Server — встроенный предохранитель; не удаляйте его без другой защиты.
  • Индексируйте столбец соединения и задавайте узкую начальную выборку для повышения производительности.

Теперь Вы умеете создавать, обходить, генерировать и защищать рекурсивные CTE от начала до конца.

Часто задаваемые вопросы

Урок «Предотвращение бесконечной рекурсии» бесплатный?

Да — полный текст урока «Предотвращение бесконечной рекурсии» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс SQL Interview Prep, подпишись на CoddyKit PRO. Курс SQL Interview Prep содержит 4 уроков всего.

Чему я научусь в уроке «Предотвращение бесконечной рекурсии»?

Обнаружение циклов, ограничение глубины и защитный механизм рекурсии, который проверяют на каждом собеседовании. Ты практикуешь SQL Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать SQL Interview Prep?

Предыдущий опыт не требуется. SQL Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.

Сколько времени занимает урок «Предотвращение бесконечной рекурсии»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке SQL Interview Prep?

Да. Каждый урок SQL Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Якорная и рекурсивная части
  2. Обход организационной структуры
  3. Генерация последовательностей чисел и дат
  4. Предотвращение бесконечной рекурсии
← Назад к SQL Interview Prep