Рекурсия (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) IF result(i, $o1, $o2, ..., $oN), где step - свойство шага.
2. Для всех значений полученного свойства вычисляет заданную агрегирующую функцию в разрезе всех его параметров, за исключением номера операции.

На данный момент для оператора рекурсии поддерживаются только два вида агрегирующих функций - SUM и OR. Последний используется в случае, когда начальное значение и шаг класса BOOLEAN. SUM используется во всех остальных случаях.

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

1. CYCLES YES - циклы допускаются. В этом случае при обнаружении цикла значение свойства будет равно максимально допустимому значению для класса значений этого свойства. Такая политика не поддерживается, когда начальное значение и шаг класса BOOLEAN.
2. CYCLES NO (по умолчанию) - циклы не допускаются. Работает аналогично предыдущей политике, но дополнительно создается ограничение, что значение полученного свойства не должно быть равно максимальному значению (которое как раз и обозначает, что для данного набора объектов образовался цикл).
3. CYCLES IMPOSSIBLE - циклы невозможны. Как правило, используется, если среди объектов есть некоторый счетчик, который на каждой итерации увеличивается и, как следствие, повториться не может.

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

Язык

Для объявления свойства, реализующего рекурсию, используется оператор 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);

// определяет на каком уровне находится child от parent, и null если не является потомком (тем самым это свойство можно использовать для определения всех child'ов)
parent = DATA Group (Group);
level 'Уровень' (Group child, Group parent) = RECURSION 1 IF child IS Group AND parent == child
                                                                  STEP 1 IF parent == parent($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;