Специфика реализации рекурсии в программных продуктах 1С

В этой статье разберём ряд характерных ситуаций, связанных с построением рекурсии.

Что такое рекурсия в программировании

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

Рекурсию применяют в тех случаях, если расчёт функции удаётся привести к её же упрощённому вызову, тот — к ещё более упрощённому и так далее до тех пор, когда результат не будет очевиден. Наиболее широкое распространение рекурсия получила в работе с древовидными структурами. В среде 1С это прежде всего операции с иерархическими справочниками.

Порядок сортировки массива с использованием бинарного дерева

Сначала разберём двоичные (бинарные) деревья. В у каждого узла могут быть не более двух дочерних элементов. Областей использования у них немало, а порядок обхода во всех случаях остаётся приблизительно одинаковым. Из любого узла возможен переход либо влево, либо вправо.

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

Постановка задачи классическая: имеется неорганизованный набор чисел, значения которого необходимо расставить в порядке возрастания.

В широком смысле в массиве не обязательно должны быть только числа. Алгоритм применяется ко всем множествам с определёнными отношениями порядка и тождества. Его логика предельно проста: корнем дерева становится первый элемент массива.

Далее значение второго элемента массива сравнивается с корнем: если второй элемент больше корня, он становится правым листом, если меньше – левым.

С оставшимися элементами действуют следующим образом:

• элемент превышает или равен текущему узлу — движемся по дереву в правую сторону;
• текущий узел больше элемента — движемся в левую сторону.

Достигнув листа, соблюдаем такой алгоритм:

• число, превышающее величину листа, само становится его правым листом;
• число, меньшее величины листа становится его левым листом.

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

Реализация алгоритма построения двоичного дерева на языке 1С

Рассмотрим работу алгоритма построения дерева наглядно на конкретных примерах.

Пример 1.  Допустим, имеется массив, изображённый на рисунке ниже.

Берём первый элемент и назначаем его корнем. Далее сравниваем все остальные элементы. 8 меньше 10 — относим его к левому листу. 2 меньше 10 и меньше 8 — формируем левый лист от восьмёрки. 3 меньше 10 и 8, однако больше 2 — образуем правый лист от двойки. 15 больше 10 — это правый лист. 12 больше 10, но меньше 15 — это левый лист от 15. Наконец, 18 превышает все остальные элементы — создаём правый лист от 15.

Вид данной логики в программном коде представлен на изображении:

Процедура построения дерева принимает два параметра: - текущий узел — конкретный узел дерева, обрабатываемый в данный момент; - значение узла — число из сортируемого массива.

Первая конструкция «Если» — это создание нового узла дерева.

Вторая конструкция «Если» — переход к левому дочернему элементу.

Блок «Иначе» — переход к правому дочернему элементу.

При этом следует обратить внимание на ряд существенных моментов.

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

Теперь необходимо собрать всё это в упорядоченный массив.

Пример 2. Предположим, что имеется дерево, изображённое на рисунке.

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

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

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

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

Рассмотрим наиболее удобный способ реализации этой идеи на следующем примере.

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

Рассмотрим одну характерную особенность данного алгоритма.

Наличие левого и правого дочерних элементов можно проверять непосредственно в теле рекурсивной функции:

В таком случае придётся формировать оператор «Если» с четырьмя ветвями.

Поэтому предпочтительнее передавать в рекурсивный вызов пустой узел и сделать этот случай терминальным. Тогда тело функции будет содержать лишь две альтернативы. Функция «Сформировать результат сортировки» принимает единственный параметр — «Текущий узел», содержащий обрабатываемый узел дерева.

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

Особенность подобного построения кода в том, что «красота требует жертв». При таком подходе в каждом листе происходят два лишних рекурсивных вызова с созданием пустого массива (обрабатывается то, чего фактически нет).

Если же внутренний узел не имеет ни левого, ни правого потомка, код точно так же обработает пустой массив. На первый взгляд это несущественно. Однако если в листе достигнута максимальная глубина стека вызовов, попытка обработки пустого узла приведёт к аварийному завершению клиентского приложения.

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

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

Пример 4. Перейдём к рассмотрению деревьев, узлы которых могут содержать более двух дочерних элементов.

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

Выводы

В этом руководстве мы изучили специфику построения рекурсии на практических примерах. Сотрудники компании «Имплекс проекты» готовы ответить на ваши вопросы по данной теме и оказать квалифицированную консультационную поддержку.