0Pricing
SQL Interview Prep · Урок

Якорная и рекурсивная части

Двухчастная структура рекурсивного CTE и принцип завершения рекурсии.

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

Зачем нужны рекурсивные CTE

Когда интервьюер показывает Вам организационную структуру, спецификацию изделия или дерево категорий и просит перечислить всех потомков, он проверяет, догадаетесь ли Вы использовать рекурсивный CTE. Обычные соединения позволяют пройти только фиксированное число уровней; рекурсия проходит на произвольную глубину.

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

Двухчастная схема

Рекурсивный CTE всегда содержит ключевое слово WITH RECURSIVE (PostgreSQL, SQLite, MySQL 8+; в SQL Server RECURSIVE опускается) и тело из двух запросов, объединённых с помощью UNION ALL:

  • Якорная часть — начальные строки, выполняется один раз.
  • Рекурсивная часть — ссылается на имя CTE, выполняется многократно.

Запомните эту схему; интервьюеры любят просить написать её с нуля.

WITH RECURSIVE cte AS (
    -- anchor member
    SELECT ...
    UNION ALL
    -- recursive member
    SELECT ... FROM cte JOIN ...
)
SELECT * FROM cte;

Что делает якорная часть

Якорная часть — это обычный запрос без ссылки на CTE. Она создаёт исходные строки — точку начала нулевого уровня. Для организационной структуры это обычно CEO (строка, у которой руководитель — NULL); для последовательности чисел — первое число.

Якорная часть выполняется ровно один раз. Её результат становится первой порцией строк, передаваемых рекурсивному шагу.

-- Anchor: the top of the hierarchy
SELECT id, name, manager_id, 1 AS depth
FROM employees
WHERE manager_id IS NULL

Что делает рекурсивная часть

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

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

-- Recursive: children of the rows found so far
SELECT e.id, e.name, e.manager_id, c.depth + 1
FROM employees e
JOIN cte c ON e.manager_id = c.id

Объединение частей

Объедините якорную и рекурсивную части с помощью UNION ALL, и СУБД автоматически выполнит итерации. Каждый проход добавляет следующий уровень, пока рекурсивная часть не вернёт ноль строк, после чего рекурсия останавливается.

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

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
)
SELECT id, name, depth FROM org ORDER BY depth, id;

Как завершается рекурсия

Рекурсия останавливается, когда рекурсивная часть создаёт новых строк. Явный счётчик итераций не нужен — соединение естественным образом исчерпывается, когда Вы достигаете листьев дерева.

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

UNION ALL и UNION

Интервьюеры часто спрашивают, почему мы используем UNION ALL, а не UNION. На это есть две причины:

  • Производительность — UNION удаляет дубликаты на каждой итерации, что требует больших затрат.
  • Корректность — в дереве дубликаты строк обычно невозможны, поэтому их удаление является напрасной работой.

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

Отслеживание глубины и пути

Два дополнительных столбца делают результаты рекурсии намного полезнее и часто запрашиваются на собеседованиях:

  • глубина — начинайте с 1 в якорной части, добавляйте 1 в рекурсивной части.
  • путь — накапливайте цепочку идентификаторов или имён, чтобы видеть маршрут от корня к узлу.

Построение path в виде строки также служит инструментом обнаружения циклов, о котором мы поговорим позже.

WITH RECURSIVE org AS (
    SELECT id, name, manager_id, 1 AS depth,
           CAST(name AS VARCHAR(1000)) AS path
    FROM employees WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, e.manager_id, o.depth + 1,
           o.path || ' > ' || e.name
    FROM employees e JOIN org o ON e.manager_id = o.id
)
SELECT name, depth, path FROM org;

Типы столбцов должны совпадать

Тонкий нюанс: якорная и рекурсивная части должны возвращать одинаковое количество столбцов с совместимыми типами. Если Вы создаёте строку path, исходное значение в якорной части необходимо привести к достаточно широкому типу (например, VARCHAR(1000)), иначе СУБД может усечь значение или выдать ошибку несовпадения типов на последующих итерациях.

Именно такие детали позволяют интервьюеру понять, что Вы действительно запускали рекурсивный CTE, а не просто читали о нём.

Пример спецификации изделия

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

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

WITH RECURSIVE bom AS (
    SELECT child_part, parent_part, 1 AS lvl
    FROM parts WHERE parent_part = 'ENGINE'
    UNION ALL
    SELECT p.child_part, p.parent_part, b.lvl + 1
    FROM parts p JOIN bom b ON p.parent_part = b.child_part
)
SELECT child_part, lvl FROM bom;

Примечания о диалектах

Краткая памятка по диалектам, которую оценят интервьюеры:

  • PostgreSQL, SQLite, MySQL 8+: WITH RECURSIVE name AS (...).
  • SQL Server: просто WITH name AS (...) — ключевое слово RECURSIVE подразумевается, а значение MAXRECURSION по умолчанию равно 100.
  • Oracle: поддерживает как рекурсивные CTE, так и старый синтаксис CONNECT BY.

Фраза «SQL Server не использует слово RECURSIVE» показывает широкий кругозор.

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

Проверьте, насколько хорошо Вы поняли двухчастную структуру.

Повторение

Теперь Вы знаете схему рекурсивного CTE:

  • WITH RECURSIVE + якорная часть + UNION ALL + рекурсивная часть.
  • Якорная часть создаёт начальные строки нулевого уровня и выполняется один раз.
  • Рекурсивная часть соединяет предыдущую итерацию с исходной таблицей и выполняется, пока не вернёт ни одной строки.
  • Используйте UNION ALL, отслеживайте depth и path, а типы столбцов сохраняйте совместимыми.

Далее: применение этой схемы для обхода реальной организационной структуры сверху вниз и снизу вверх.

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

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

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

Чему я научусь в уроке «Якорная и рекурсивная части»?

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

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

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

Сколько времени занимает урок «Якорная и рекурсивная части»?

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

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

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

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

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