Введение в рекурсию

Иерархические и рекурсивные запросы в SQL Server

Jasmin Ludolf

Content Developer

Что такое рекурсия?

Рекурсия — это использование процедуры, подпрограммы, функции или алгоритма, который вызывает сам себя один или несколько раз до выполнения заданного условия

Анимация, иллюстрирующая свойство рекурсии вызывать саму себя многократно.

Пример рекурсии из реальной жизни

Генеалогическое дерево — найти всех отцов за последние 5 поколений

Сведите задачу к меньшей задаче того же типа
1. Полная задача: найти все пять поколений
2. Меньшая задача: найти отца, найти отца отца, ...
Ограничьте количество шагов

Рекурсивное свойство Ханойской башни.

Факты о рекурсии

Преимущества:

Позволяет решать задачи рекурсивным способом
Код легко читать и понимать
Рекурсия ограничивается условием завершения

Недостатки:

Низкая скорость выполнения

Пример рекурсии — сумма чисел

Математическое определение

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

number = 1 
    for iteration = 1
number = number + (iteration - 1) 
    for iteration > 1

Сумма чисел до 5 равна:

1+2+3+4+5 = 15

Пример рекурсии — сумма чисел

Рекурсия в SQL: Общее табличное выражение — CTE

WITH calculate_SumOfNumber AS
     ( -- Initial Query
    SELECT 1 AS iteration, 1 AS SumOfNumber

     UNION ALL
     -- Recursive Part 
     SELECT iteration + 1, SumOfNumber + (iteration + 1)
         FROM calculate_SumOfNumber

         WHERE iteration < 6
     )

SELECT SumOfNumber 
    FROM calculate_SumOfNumber

Давайте потренируемся!

Иерархические и рекурсивные запросы в SQL Server