Рекурсия (RECURSION)

Оператор рекурсии создает свойство, которое последовательно выполняет две операции:

1. Рекурсивно строит промежуточное свойство (result) с дополнительным первым параметром (номером операции) следующим образом:
   1. result(0, o1, o2, ..., oN) = initial(o1, ..., oN), где initial - начальное свойство.
   2. result(i+1, o1, o2, ..., oN) = step(o1, ..., oN, $o1, $o2, ..., $oN) * result(i, $o1, $o2, ..., $oN) для числового класса значений и result(i+1, o1, o2, ..., oN) = step(o1, ..., oN, $o1, $o2, ..., $oN) IF result(i, $o1, $o2, ..., $oN) для остальных, где step - свойство шага, а $o1, ..., $oN обозначают значения параметров на предыдущей итерации. Если один и тот же набор объектов получается на итерации из нескольких наборов предыдущей итерации, каждый из них даёт отдельное значение.
2. Для всех значений полученного свойства вычисляет заданную агрегирующую функцию в разрезе всех его параметров, за исключением номера операции.

Агрегирующая функция выбирается автоматически по классу значений initial/step: если они принадлежат числовому классу, используется SUM, и класс результата — тот же числовой класс; в остальных случаях (как правило, при классе BOOLEAN) используется OR, и класс результата — тот же не-числовой класс (кроме политики CYCLES NO, см. ниже). Таким образом, числовая рекурсия суммирует по всем путям от начальных наборов объектов к данному значение начального свойства в начале пути, умноженное на произведение значений шага вдоль пути. При начальном значении 1 и постоянном шаге 1 результат — количество таких путей (в дереве, где к каждому набору ведёт один путь, всегда 1), при начальном значении 1 и постоянном шаге 2 — сумма 2 в степени длины пути (в дереве — 2 в степени расстояния до предка).

Отметим, что на некоторой итерации наборы объектов могут начать повторяться. В этом случае будем говорить что образуется цикл. Существует три политики работы с циклами:

1. CYCLES YES - циклы допускаются. В этом случае при обнаружении цикла (набор объектов повторяется на пути итераций) для повторившегося набора добавляется значение-маркер — округлённый квадратный корень из максимального значения класса результата (46341 для INTEGER, 3037000500 для LONG), — и следующие итерации из строки с маркером не строятся; итоговое значение для набора — сумма маркера с остальными накопленными для него значениями, поэтому оно может быть больше маркера. Для рекурсии со значениями класса BOOLEAN маркера нет: повторяющиеся наборы объектов отбрасываются, и цикл не меняет результат.
2. CYCLES NO (по умолчанию) - циклы не допускаются. Работает аналогично предыдущей политике, но дополнительно создается ограничение, запрещающее значение полученного свойства больше половины маркера цикла. Это числовой порог, поэтому его может превысить и достаточно большое значение рекурсии без циклов. Для initial/step класса BOOLEAN при этой политике каждое значение, не равное NULL, заменяется числом 1, а классом результата становится LONG.
3. CYCLES IMPOSSIBLE - циклы невозможны. Как правило, используется, если среди объектов есть некоторый счетчик, который на каждой итерации увеличивается и, как следствие, повториться не может.

При использовании оператора рекурсии важно удостовериться в том, что рекурсивное построение коллекции будет конечно, то есть значение шага рано или поздно станет NULL (как правило, речь идет о политике CYCLES IMPOSSIBLE, так как в противном случае рекурсия остановится при первом найденном цикле). Если это условие не выполнено, операция будет принудительно остановлена в зависимости от настроек SQL сервера.

Для иерархии, заданной свойством parent[class], типовые рекурсивные свойства — предок, уровень, число потомков, полное имя от корня — даёт готовый системный модуль Hierarchy.

Язык

Для объявления свойства, реализующего рекурсию, используется оператор RECURSION.

Примеры

CLASS Node;
edge = DATA BOOLEAN (Node, Node);

// итерация по integer от from к to (это свойство по умолчанию входит в модуль System)
iterate(i, from, to) = RECURSION i==from AND from IS INTEGER AND to IS INTEGER STEP i==$i+1 AND i<=to CYCLES IMPOSSIBLE;

// считает количество различных путей от a до b в графе
pathes 'Кол-во путей' (a, b) = RECURSION 1 AND a IS Node AND b==a STEP 1 IF edge(b, $b);

// не NULL, если parent — предок группы child или сама эта группа (тем самым свойство отбирает всех потомков parent);
// числовое значение — количество путей от child к parent по свойству parent, в дереве всегда 1
parent = DATA Group (Group);
isParent 'Является родителем' (Group child, Group parent) = RECURSION 1 IF child IS Group AND parent == child
                                                                      STEP 1 IF parent == parent($parent);

// уровень группы в иерархии — количество её предков вместе с ней самой (для корня 1)
level 'Уровень' (Group child) = GROUP SUM 1 IF isParent(child, Group parent);

// числа Фибоначчи, свойство высчитывает все числа Фибоначи до значения to, (после будет возвращать null)
fib(i, to) = RECURSION 1 IF (i==0 OR i==1) AND to IS INTEGER STEP 1 IF (i==$i+1 OR i==$i+2) AND i<to CYCLES IMPOSSIBLE;