Рекурсия в 1С и управление деревом значений
Термин «рекурсия» используется во многих областях знаний. В программировании рекурсия – вызов процедуры (функции) из нее же самой. Различают простую и сложную рекурсию. При простой рекурсии некоторая процедура А вызывает сама себя, пока не выполниться заданное условие выхода, или же бесконечно. В случае сложной рекурсии процедура А вызывает процедуру Б, которая опять вызывает процедуру А, и так далее до выполнения условия выхода или бесконечно. В сложной рекурсии может участвовать и больше двух процедур или функций.
Организовать рекурсию средствами встроенного языка 1С Предприятия очень легко. Вот пример простой рекурсии:
Процедура ПроцедураА () ПроцедураА (); КонецПроцедуры
А это сложная рекурсия:
Процедура ПроцедураА () ПроцедураБ (); КонецПроцедуры
Процедура ПроцедураБ () ПроцедураА (); КонецПроцедуры
Оба фрагмента кода приведены исключительно для примера. При попытке их выполнить возникнет бесконечный цикл и, как результат, произойдет зависание системы, поскольку не задано условие выхода. Создадим рекурсию с условием выхода:
Процедура ВывестиЧисла ( пЧисло ) Если пЧисло <= 100 Тогда Сообщить ( Строка ( пЧисло )); пЧисло = пЧисло + 1 ; ВывестиЧисла ( пЧисло ); Иначе Возврат; КонецЕсли; КонецПроцедуры
Этот фрагмент кода выведет в окно служебных сообщений 1С Предприятия числа от 1 до 100. После этого выполниться условие выхода и программа будет завершена. Процедура вызовет сама себя ровно 100 раз. Количество таких вызовов процедуры или функции называется глубиной рекурсии.
Реализация рекурсивных вызовов функций и процедур в практически применяемых языках и средах программирования, использует механизм стека вызовов — адрес возврата и локальные переменные функции записываются в стек, благодаря чему каждый следующий рекурсивный вызов этой функции пользуется своим набором локальных переменных и за этот счёт работает корректно.
Оборотной стороной этого довольно простого по структуре механизма является то, что рекурсивные вызовы не бесплатны — на каждый рекурсивный вызов требуется некоторое количество оперативной памяти компьютера, и при чрезмерно большой глубине рекурсии может наступить переполнение стека вызовов. Вследствие этого обычно рекомендуется избегать рекурсивных программ, которые приводят к слишком большой глубине рекурсии.
Пример с выводом чисел естественно не является оптимальным, он приведен только в целях демонстрации. На практике в этом случае гораздо удобнее использовать цикл. Рекурсию следует использовать там, где с помощью циклов решать задачу нецелесообразно.
В 1С Предприятии 8.х рекурсия может быть использована для решения задач управления деревом значений. Например, мы интерактивно изменяем пометку элемента, который находиться на одном из верхних уровней дерева значений. В таком случае пометки должны программно устанавливаться (или сниматься) и для всех подчиненных ему элементов, находящихся на более низких уровнях дерева.
Если максимальное количество уровней дерева известно, то эта задача может быть решена следующим образом:
Процедура ИзменитьПометкиПодчиненных ( пГлавный ) Подчиненные1 = пГлавный . Строки ;
// Первый уровень подчиненных Для Каждого Подчиненный1 Из Подчиненные1 Цикл Подчиненный1 . Пометка = пГлавный . Пометка ; Подчиненные2 = Подчиненный1 . Строки ;
// Второй уровень подчиненных Для Каждого Подчиненный2 Из Подчиненные2 Цикл Подчиненный2 . Пометка = пГлавный . Пометка ; Подчиненные3 = Подчиненный2 . Строки ;
// Третий уровень подчиненных Для Каждого Подчиненный3 Из Подчиненные3 Цикл Подчиненный3 . Пометка = пГлавный . Пометка ; КонецЦикла; КонецЦикла; КонецЦикла; КонецПроцедуры
Приведенная выше процедура устанавливает или снимает пометки у четырехуровневого дерева. Обход элементов дерева выполняется в трех вложенных друг в друга циклах. В качестве параметра «пГлавный» мы передаем строку верхнего уровня дерева значений, затем получаем подчиненные строки переданной строки и устанавливаем пометки. Затем получаем подчиненные строки каждой подчиненной строки, снова устанавливаем пометки, и т. д.
А если усложнить задачу? Если максимальное количество уровней дерева неизвестно или так велико, что использовать вложенные циклы просто неэффективно, код получиться слишком громоздкий, да еще и повторяющийся? Ведь, по сути, для каждого уровня дерева значений выполняется одна и та же последовательность действий. Вот тут нам на помощь и придет рекурсия. В данном случае достаточно будет использовать простую рекурсию.
Процедура ИзменитьПометкиПодчиненных ( пГлавный ) Подчиненные = пГлавный . Строки ; Для Каждого Подчиненный Из Подчиненные Цикл Подчиненный . Пометка = пГлавный . Пометка ; ИзменитьПометкиПодчиненных ( Подчиненный ); КонецЦикла; КонецПроцедуры
Вместо создания отдельного вложенного цикла для каждого уровня дерева, мы выполняем вызов этой же самой процедуры. Результат налицо, код получился гораздо компактнее а кроме того, нам не придется описывать каждый уровень вложенности дерева. Следовательно, используя рекурсию, мы можем работать с деревьями, имеющими неограниченное количество уровней вложенности.
Впрочем, использование рекурсии не является единственным решением для этой задачи. Существует еще один оригинальный алгоритм - поуровневый обход дерева (предложен Арчибальдом).
Процедура ИзменитьПометкиПодчиненных ( пГлавный ) УровеньА = Новый Массив ; УровеньБ = Новый Массив ; УровеньА . Добавить ( пГлавный ); Пока НЕ ( УровеньА . Количество () = 0 ) Цикл Для Каждого СтрокаДерева Из УровеньА Цикл СтрокаДерева . Пометка = пГлавный . Пометка ; Для Каждого СтрокаДереваПодчиненная из СтрокаДерева . Строки Цикл УровеньБ . Добавить ( СтрокаДереваПодчиненная ); КонецЦикла; КонецЦикла; УровеньА = УровеньБ ; УровеньБ = Новый Массив ; КонецЦикла; КонецПроцедуры
Здесь при обходе строк верхнего уровня дерева (А) запоминаются ссылки на строки нижнего уровня дерева (Б). Затем происходит перемещение на один уровень вниз и так далее, до тех пор, пока не будет пройдено все дерево. В качестве хранилищ для ссылок на строки используются массивы.
Этот вариант хорош тем, что может быть использован для работы с деревьями с неограниченным количеством уровней вложенности. Кроме того, он лишен недостатка рекурсии, связанного с возможностью переполнения стека.
Какой из описанных механизмов наиболее оптимален с точки зрения быстродействия? Ответ на этот вопрос может дать замер производительности.
Для тестирования производительности мною была использовано дерево значений, имеющее четыре уровня вложенности и состоящее из 1416 строк. Во время тестирования интерактивно снималась пометка с корневого элемента дерева и, соответственно, программно снимались пометки всех его подчиненных элементов.
При прочих равных условиях выполнение кода с использованием рекурсии заняло 0,086753 секунды, выполнение кода с использованием нескольких вложенных циклов – 0,050159 секунды, выполнение кода поуровневого обхода дерева – 0,087718 секунды.
Естественно дерево, на котором проводилось тестирование, было сравнительно небольшим. В данном случае доли секунды разницы не имеют особенного значения. Но при использовании очень больших деревьев значений быстродействие играет далеко не последнюю роль.
Отсюда можно сделать вывод, что обход дерева в нескольких вложенных циклах обеспечивает большее быстродействие, чем два других варианта. Если количество уровней вложенности дерева относительно небольшое, а количество строк большое то целесообразно использовать именно этот вариант. Если же количество уровней дерева большое (или неизвестное) а строк у него немного, то нужно использовать один из двух других вариантов.