Рекурсия в 1С и управление деревом значений

02.07.09

Разработка - Механизмы платформы 1С

Термин «рекурсия» используется во многих областях знаний. В программировании рекурсия – вызов процедуры (функции) из нее же самой. Статья рассказывает об использовании рекурсии в 1С Предприятии для работы с деревом значений.

 

Термин «рекурсия» используется во многих областях знаний. В программировании рекурсия – вызов процедуры (функции) из нее же самой. Различают простую и сложную рекурсию. При простой рекурсии некоторая процедура А вызывает сама себя, пока не выполниться заданное условие выхода, или же бесконечно. В случае сложной рекурсии процедура А вызывает процедуру Б, которая опять вызывает процедуру А, и так далее до выполнения условия выхода или бесконечно. В сложной рекурсии может участвовать и больше двух процедур или функций.

Организовать рекурсию средствами встроенного языка 1С Предприятия очень легко. Вот пример простой рекурсии:

Процедура ПроцедураА()
   
ПроцедураА();
КонецПроцедуры

 А это сложная рекурсия:

Процедура ПроцедураА()
   
ПроцедураБ();
КонецПроцедуры

Процедура
ПроцедураБ()
   
ПроцедураА();
КонецПроцедуры

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

Процедура ВывестиЧисла(пЧисло)
    Если
пЧисло <= 100 Тогда
       
Сообщить(Строка(пЧисло));
       
пЧисло = пЧисло + 1;
       
ВывестиЧисла(пЧисло);
    Иначе
        Возврат;
    КонецЕсли;
КонецПроцедуры

ВывестиЧисла(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 секунды.

Естественно дерево, на котором проводилось тестирование, было сравнительно небольшим. В данном случае доли секунды разницы не имеют особенного значения. Но при использовании очень больших деревьев значений быстродействие играет далеко не последнюю роль.

Отсюда можно сделать вывод, что обход дерева в нескольких вложенных циклах обеспечивает большее быстродействие, чем два других варианта. Если количество уровней вложенности дерева относительно небольшое, а количество строк большое то целесообразно использовать именно этот вариант. Если же количество уровней дерева большое (или неизвестное) а строк у него немного, то нужно использовать один из двух других вариантов.

           

http://www.infostart.ru/projects/4059/

 

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

http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F

См. также

Поинтегрируем: сервисы интеграции – новый стандарт или просто коннектор?

Обмен между базами 1C Администрирование СУБД Механизмы платформы 1С Платформа 1С v8.3 Бесплатно (free)

В платформе 8.3.17 появился замечательный механизм «Сервисы интеграции». Многие считают, что это просто коннектор 1С:Шины. Так ли это?

11.03.2024    4468    dsdred    53    

70

Как готовить и есть массивы

Механизмы платформы 1С Платформа 1С v8.3 Бесплатно (free)

Все мы используем массивы в своем коде. Это один из первых объектов, который дают ученикам при прохождении обучения программированию. Но умеем ли мы ими пользоваться? В этой статье я хочу показать все методы массива, а также некоторые фишки в работе с массивами.

24.01.2024    5280    YA_418728146    25    

63

Планы обмена VS История данных

Обмен между базами 1C Механизмы платформы 1С Платформа 1С v8.3 Бесплатно (free)

Вы все еще регистрируете изменения только на Планах обмена и Регистрах сведений?

11.12.2023    6396    dsdred    36    

111

1С-ная магия

Механизмы платформы 1С Бесплатно (free)

Язык программирования 1С содержит много нюансов и особенностей, которые могут приводить к неожиданным для разработчика результатам. Сталкиваясь с ними, программист начинает лучше понимать логику платформы, а значит, быстрее выявлять ошибки и видеть потенциальные узкие места своего кода там, где позже можно было бы ещё долго медитировать с отладчиком в поисках источника проблемы. Мы рассмотрим разные примеры поведения кода 1С. Разберём результаты выполнения и ответим на вопросы «Почему?», «Как же так?» и «Зачем нам это знать?». 

06.10.2023    18465    SeiOkami    46    

118

Дефрагментация и реиндексация после перехода на платформу 8.3.22

Механизмы платформы 1С Платформа 1С v8.3 Бесплатно (free)

Начиная с версии платформы 8.3.22 1С снимает стандартные блокировки БД на уровне страниц. Делаем рабочий скрипт, как раньше.

14.09.2023    12077    human_new    27    

74

Валидация JSON через XDTO (включая массивы)

WEB-интеграция Универсальные функции Механизмы платформы 1С Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

При работе с интеграциями рано или поздно придется столкнуться с получением JSON файлов. И, конечно же, жизнь заставит проверять файлы перед тем, как записывать данные в БД.

28.08.2023    8802    YA_418728146    6    

141

Внешние компоненты Native API на языке Rust - Просто!

Механизмы платформы 1С Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

Внешние компоненты для 1С можно разработывать очень просто, пользуясь всеми преимуществами языка Rust - от безопасности и кроссплатформенности до удобного менеджера библиотек.

20.08.2023    6273    sebekerga    54    

94

Все скопируем и вставим! (Буфер обмена в 1С 8.3.24)

Механизмы платформы 1С Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

Рассмотрим новую возможность 8.3.24 и как её можно эффективно использовать

27.06.2023    15972    SeiOkami    31    

103
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
96. YVolohov 721 02.07.09 17:03 Сейчас в теме
Спасибо за поддержку. Скандалить в любом случае не буду, разве что нарвусь на откровенное хамство )))
А статью я еще доделаю. В итоге должны быть описаны все возможные варианты решения проблемы.
Evg-Lylyk; +1 Ответить
97. venger 2121 02.07.09 21:12 Сейчас в теме
(96) > разве что нарвусь на откровенное хамство

А что скандалить, да я понимаю, что рекурсия красиво выглядит и сам через такое проходил, очень не хотелось отказываться от нее во многих случаях, вот и Вы ищете чем оправдать (я тоже с большим "не удовольствием" принял этот факт), но факт остается фактом, я с самого начала в первых постах все сказал...

По этому поводу есть анекдот:
Программа по заявкам по кацапскому радио:
"Пишет нам ученик 9го класса с.ш. г. Ленинграда Вася Пупкин и просит поставить для него песню "Валенки" в исполнении Руслановой-пожалуйста"
Прошло 5 лет, та же передача:
"Пишет нам студент Вася Пупкин - песню " Валенки " в исп. Руслановой - слушайте".
Прошло 20 лет, та же передача:
"Пишет нам директор предприятия Василий Васильевич Пупкин и просит поставитть Фугу ля минор И-С. Баха. Василий Васильевич не вые@ывайтесь и слушайте свои "Валенки".

Мораль такова, что иногда нет смысла выпендриваться - только хуже будет:-)
98. Evg-Lylyk 4559 03.07.09 02:03 Сейчас в теме
(97) На мой взгляд выпендривание это как раз замена рекурсии, я про случай с обходом дерева. Согласен что рекурсию понять сложнее чем цикл, но когда понимаешь используешь только ее т.к. на самом деле в определенных случаях это более читабельный вариант
(90) проверьте пожалуйста быстродействие в сравнении с рекурсией, а то тут многие видят это как "эффективную" :)замену рекурсии. Не знаю как студенты, но мне честно трудно понять что там делается.

100. Evg-Lylyk 4559 03.07.09 02:13 Сейчас в теме
Для яростных "заменьшиков" рекурсии: Понятно что все можно заменить простыми операциями тот же цикл можно заменить на если, а надо ли.
102. CheBurator 3119 03.07.09 04:05 Сейчас в теме
В качестве практического использования рекурсии может быть приведена обработка "Универсальная сортировка ТЧ документа с произвольным уровнем вложенности сортируемого реквизита": http://www.infostart.ru/projects/4340/
103. YVolohov 721 03.07.09 11:04 Сейчас в теме
Если честно, то мне уже здорово надоел этот спор. В любом случае каждый будет использовать то что ему больше нравиться. В последнем обновлении статьи я описал три возможных варианта обхода дерева + сделал замеры производительности для каждого из них. На этом закрываю тему, по крайней мере для себя. Тем более что времени и так не хватает, работаю над очень интересным проектом, думаю скоро закончить и выложить.
105. Altair777 644 03.07.09 11:16 Сейчас в теме
(103)
> В любом случае каждый будет использовать то что ему больше нравиться

А вот это не правильно. Нужно использовать то, что лучше подходит в каждой конкретной ситуации.
А факторов много:
1) Надежность
2) Скорость работы
3) Скорость разработки
4) Легкость доработок
5) Эстетика :-)
104. Арчибальд 2706 03.07.09 11:10 Сейчас в теме
В связи с исчезновением из статьи ложных утверждений, минус снимаю :))
106. almas 254 03.08.09 22:28 Сейчас в теме
Я тихо фигею. Мне сия дискусия напомнила байку про мудрецов, которые у палки начало и конец искали.
YVolohov - спасибо за корректный пример кода. После института многое из головы улетает напрочь, а тут просто доступно и популярно.
Куча 1с-ников не хотят напрягать мозги и когда их код читаешь -"тихо шифером шурша...". Однозначно +
107. YVolohov 721 04.08.09 11:43 Сейчас в теме
(106) Сия дискуссия есть наглядный пример, как надо убивать время оплаченное работодателем ))
Впрочем, на Мисте вон еще хуже. Тут хотя бы в тему дискуссия, а там обсуждаются вопросы типа "Сколько весит дырка от бублика ?" и "Какова скорость сферического коня в вакууме ?"
110. igor_gk 49 20.08.09 11:49 Сейчас в теме
Вот сейчас нужно решить задачку вроде как пообъемнее, чем простой обход дерева. Ну и думаю рекурсия иле еще как... Есть док1 формирующий сумму, в его ТЧ есть доки такого же вида со своими суммами и они влияют на сумму док1, в свою очередь в ТЧ доков, упоминаемых в ТЧ док1, есть свои доки такого же вида, влияющие на их суммы... ну т.д. Т.е. неизвестно заранее количество уровней, в то же время вовсе не исключена ситуация "зацикленности" (в док1 есть док, в котором ссылка на док1 или как-то еще более глубоко)...
Вот сижу и думаю - если рекурсия, то код выглядеть будет красивше, но при отладке можно и моск сломать... Да и ресурсов оно сожрет....
111. YVolohov 721 20.08.09 16:17 Сейчас в теме
(110)
Для того чтобы не зациклить систему на какой нибудь перекрестной ссылке тебе нужно будет вести список всех обойденных документов и контролировать наличие каждой новой ссылки в этом списке.
Можно впрочем сделать и по другому. Контролировать дату и время документа, добавляемого в табличную часть при заполнении документа, чтобы его дата/время были меньшими чем у главного документа. Тогда перекрестных ссылок возникать не будет.
Что касается обхода документов, то можно использовать как рекурсию так и цикл. Лично я воспользовался бы рекурсией, код будет более удобочитаемый.

И самое главное, возможно у задачи есть более простое решение. А то вся эта куча документов с перекрестными ссылками выглядит достаточно извратно. Напиши для чего все это. Думаю найдется решение попроще.
112. Aydrey 08.11.11 16:05 Сейчас в теме
Большое спасибо. простой и ничего лишнего. спасибо за сэкономленное время.
113. rom-x 152 24.12.11 17:39 Сейчас в теме
Поделюсь и своим кодом, нужно было собрать в Сз все подчиненные группы выбранной группы в форме.
Сз1.ДобавитьЗначение(Номенклатура.Код);
Пока Сз1.РазмерСписка() <> 0 Цикл
	Для Ин=1 По Сз1.РазмерСписка() Цикл
		Ссылка = Сз1.ПолучитьЗначение(ин);
		сНом.ВыбратьЭлементы();
		Пока сНом.ПолучитьЭлемент() = 1  Цикл
			Если (Строка(сНом.Родитель.Код) = Ссылка) И (сНом.ЭтоГруппа() = 1) Тогда
				Сз2.ДобавитьЗначение(сНом.Код, сНом.Наименование);
			КонецЕсли;
		КонецЦикла;
	КонецЦикла;
	Сз1 = Сз2;
	Для Ин=1 По Сз2.РазмерСписка() Цикл
	   Сз3.ДобавитьЗначение(Сз2.ПолучитьЗначение(ин));
	КонецЦикла;
	Сз2 = СоздатьОбъект("СписокЗначений");
КонецЦикла
Показать
114. vkt 125 11.02.15 11:24 Сейчас в теме
http://www.infostart.ru/projects/4059/ - циклическая ссылка, если не ошибаюсь?
115. Stradivari 157 13.02.19 10:36 Сейчас в теме
Спасибо. Статья помогла!)
Оставьте свое сообщение