В теме статьи обозначено «для начинающих», чтобы Гуру сильно не «пинали» за очевидные для них понятия. Тем не менее, объяснять рекурсию будем на основе понятий, которые ранее явно не часто были обозначены (блоки кода в теле рекурсивной функции).
Мы будем говорить о рекурсии в программировании. Не будем обсуждать, что такое рекурсия, и какая она бывает. На эту тему очень много статей и книг. Например, книга «Введение в рекурсивное программирование», автор Мануэль Рубио-Санчес, посвящена только рекурсии на 436 страницах.
Обычно есть вызывающая процедура и собственно рекурсивная функция. Собственно, теоретическая часть статьи заключается в изложении структуры рекурсивной функции. Изучать рекурсию проще используя процедуру с параметрами, а не функцию, возвращающую значение.
Листинг 1
Для деревьев вместо условия применяется цикл. Деревья рассмотрим ниже.
Задача - научиться понимать эти пять блоков команд.
Самая известная тема для рекурсии — это расчет факториала:
Функция Факториал(n)
Возврат ?(Число(n) <= 1, 1, n * Факториал (n -1)); (2)
КонецФункции
Листинг 2
Очень красивый код, но не очень понятный …
Напишем код расчета факториала согласно нашей модели (Листинг 1):
&НаКлиенте
Процедура ВычислитьФакториал()
Ф=1;
к=0;
н=4;
Факториал (к, н, Ф);
Сообщить(Ф);
КонецПроцедуры
Процедура Факториал (к, н, Ф)
к=к+1;
Если к <= н Тогда
Ф=Ф*к;
Факториал (к, н, Ф);
Иначе
Возврат;
КонецЕсли;
КонецПроцедуры
Не так красиво, как (2), но мы учимся.
к – счетчик;
н – значение для вычисления факториала;
Ф – факториал (для н=4 будет 24).
Код достаточно понятный. Заметим только то, что Ф рассчитывается на прямом пути. На обратном пути (Возврат) – ничего не происходит. Полезно отследить изменение параметров в отладчике:
Здесь использованы блоки 1 и 2.
Блок1 – как правило на практике, нужен для подготовки Условия.
Блок2 – нужен для подготовки вызова рекурсивной процедуры (функции);
Теперь можно изменить процедуру Факториал убрать параметр к и приблизить её к каноническому виду (1).
&НаКлиенте
Процедура ВычислитьФакториал()
н=4;
Ф=1;
Сообщить Факториал (н, Ф);
КонецПроцедуры
Процедура Факториал (н, Ф)
Если н > 0 Тогда
Ф=Ф*н;
Факториал (н - 1, Ф);
КонецЕсли;
КонецПроцедуры
Блок1 – исчез.
На следующем шаге заменим процедуру на функцию и уберем вычисление Ф в Блоке2.
Для полного понимания предварительно рассмотрим следующий вариант:
Функция Факториал (н, Ф)
Если н > 0 Тогда
//Блок2
Останов=Истина;
Факториал (н -1, Ф*н);
//Блок3;
Останов=Истина;
КонецЕсли;
//Блок5
Останов=Истина;
Возврат Ф;
КонецФункции
Возвращаться будет 1.
Строки Останов = Истина добавлены для анализа переменных Ф и н в отладчике. Теперь нет параметра Ф в виде ссылки и возвращается локальное значение Ф, которое было зафиксировано при первом входе в рекурсию.
Исправим, добавим возврат переменной Ф. И увидим, что такое локальная переменная в рекурсивной функции – в отладчике. Это важно понимать.
Функция Факториал (н, Ф)
Если н > 0 Тогда
//Блок2
Останов=Истина;
Ф = Факториал (н -1, Ф*н);
//Блок3;
Останов=Истина;
КонецЕсли;
//Блок5
Останов=Истина;
Возврат Ф;
КонецФункции
На рисунке выше момент, когда вернулись в функцию, в которую входили с н = 2 и Ф = 12. Значение Ф сохранилось как для локальной переменной.
Это момент, когда еще не присвоено Ф возвращаемое значение функцией Факториал.
И вот на следующем шаге Ф переприсваивается.
В итоге функция отработает правильно.
Здесь мы не пишем функцию факториал, мы смотрим для чего нужны Блоки 1-5, как ведут себя переменные.
Рассмотрим простые примеры рекурсий в 1С.
// <Описание функции>
//Возвращает количество группировок в настройках варианта макета СКД
// Возвращаемое значение:
// Кг – Число
Функция КоличествоГруппировокВНастройке ()
Кг=0;
СтруктураГруппировок=Настройки.Структура;
КоличествоГруппировок (Кг, СтруктураГруппировок);
Возврат Кг;
КонецФункции // КоличествоГруппировокВНастройке ()
Процедура КоличествоГруппировок (Кг, СтруктураГруппировок)
Если СтруктураГруппировок.Количество() >0 Тогда
СтруктураГруппировок=СтруктураГруппировок [0].Структура;
Кг=Кг + 1;
КоличествоГруппировок (Кг, СтруктураГруппировок);
Иначе
Возврат;
КонецЕсли;
КонецПроцедуры
Эта универсальная функция полезна для фиксации шапки отчета при программном выводе его:
ТабДок.ФиксацияСверху = Кз+Кг;
Здесь Кз - высота заголовка, Кг – высота шапки.
Функция упрощена для примера. Настройки – настройки варианта макета, объявленные в Перем:
СхемаКомпоновкиДанных = ОтчетОбъект.ПолучитьМакет(СхемаИмя);
Вариант = СхемаКомпоновкиДанных.ВариантыНастроек[0];
Настройки = Вариант.Настройки;
Рекурсивная функция написана в стиле листинга 1 и предельно понятна.
Основное применение рекурсии нашли при работе с деревьями. В 1С это в основном работа с иерархическими справочниками.
В теории деревьев различают корень, ветки и листья. Корень (ствол) это один элемент.
В 1С корня в классическом понимании у справочника нет. Корень — это сам иерархический справочник. Группы самого верхнего уровня имеют значение метода Уровень () = 0.
Рассмотрим пример определения самого старшего родителя для произвольного элемента справочника.
Каждый узел дерева имеет в точности одного родителя, за исключением корня, у которого нет родителей.
Это значит, что при движении по дереву вверх циклы не понадобятся.
&НаСервереБезКонтекста
Функция ПолучитьРодителя(ЭлементСправочника)
Если ЭлементСправочника.Уровень() = 0 Тогда
Возврат ЭлементСправочника;
КонецЕсли;
Возврат ПолучитьРодителя(ЭлементСправочника.Родитель);
КонецФункции
Рассмотри пример использования рекурсий при обходе иерархического справочника с целью расчета себестоимости объектов строительства.
Предмет примера:
Есть объекты строительства. Объекты связаны иерархической моделью.
Нижние уровни дерева (листья) имеют прямые затраты. Их родители имеют косвенные затраты, которые нужно распределить на нижний уровень пропорционально прямым затратам объектов (листьев).
Прямые затраты – стоимость оборудования, косвенные – работы, необходимые для монтажа и ввода в эксплуатацию оборудования.
Вот пример из реальной БД:
Видим, что справочник «Объектов строительства» имеет до 7 уровней иерархии. В модели – есть объекты, которые будут приниматься к учету – основные средства. И есть работы, затраты которых нужно распределить:
Для решения задачи разберем алгоритм на следующей модели:
Рис. 1. Схема дерева
Рис.2. Дерево в справочнике объектов
Три уровня иерархии. Шесть объектов строительства с прямыми затратами и три с косвенными (группы).
Рассчитаем косвенные для объектов вручную.
База распределения для объекта Объект1 = 3000+2000 = 5000;
Косвенные от Объекта1:
для Объекта11 косвенные = 500 * 3000 / 5000 = 300.
для Объекта12 косвенные = 500 * 2000 / 5000 = 200.
База распределения для объекта Объект2 = 3000+2000+1000 = 6000;
Косвенные от Объекта2:
для Объекта21 косвенные = 600 * 3000 / 6000 = 300.
для Объекта22 косвенные = 600 * 2000 / 6000 = 200.
для Объекта23 косвенные = 600 * 1000 / 6000 = 100.
База распределения для объекта Объект0 – 5000+6000+1000 = 12000;
От Объекта0:
Для Объекта01 косвенные = 2400 * 1000 / 12000 = 200.
Для Объекта11 косвенные = 2400 * 3000 / 12000 = 600.
Для Объекта12 косвенные = 2400 * 2000 / 12000 = 400.
Для Объекта21 косвенные = 2400 * 3000 / 12000 = 600.
Для Объекта22 косвенные = 2400 * 2000 / 12000 = 400.
Для Объекта23 косвенные = 2400 * 1000 / 12000 = 200.
В итоге косвенные:
Для Объекта01 косвенные = 200
Для Объекта11 косвенные = 600 + 300 = 900
Для Объекта12 косвенные = 400 + 200 = 600
Для Объекта21 косвенные = 600 + 300 = 900
Для Объекта22 косвенные = 400 + 200 = 600
Для Объекта23 косвенные = 200 + 100 = 300
==================================
Итого косвенных 3500
Листинг 3
Нужно сформировать запрос с Итогами, обязательно указать тип итогов «Элементы и иерархия».
В запросе должно быть так:
ИТОГИ ПО Ссылка ИЕРАРХИЯ
Следующий момент - куда лучше выгружать данные:
-
ВыборкаИзРезультатаЗапроса
-
ДеревоЗначений
Мы выбираем дерево, потому что
-
В отладчике можно посмотреть данные.
-
Код более понятный – объект, строки, цикл.
-
Есть возможность реквизиты дерева использовать для алгоритма (записывать в реквизиты данные).
В интернете много статей обхода дерева как такового. А вот обход дерева, сгенерированного запросом, рассмотрен крайне скупо. Для выборки - статей написано много.
Поэтому рассмотрим алгоритм обхода дерева вниз и вверх - подробно.
&НаСервере
Перем ОбъектыДляПриемки;
&НаСервере
Процедура КосвеныеОбъектовНаСервере()
ОбъектыДляПриемки = Новый ТаблицаЗначений;
ОбъектыДляПриемки.Колонки.Добавить("Объект", Новый ОписаниеТипов("СправочникСсылка.ОбъектыСтроительства"));
ОбъектыДляПриемки.Колонки.Добавить("Косвенные", Новый ОписаниеТипов("Число"));
Запрос = Новый Запрос;
Запрос.Текст =
"ВЫБРАТЬ
| ОбъектыСтроительства.Ссылка КАК Ссылка,
| ОбъектыСтроительства.Прямые КАК Прямые,
| ОбъектыСтроительства.Косвенные КАК Косвенные
|ИЗ
| Справочник.ОбъектыСтроительства КАК ОбъектыСтроительства
|ГДЕ
| ОбъектыСтроительства.Ссылка В ИЕРАРХИИ(&Ссылка)
|ИТОГИ
| СУММА(Прямые)
|ПО
| Ссылка ИЕРАРХИЯ";
Дерево = Запрос.Выполнить().Выгрузить(ОбходРезультатаЗапроса.ПоГруппировкамСИерархией);
Рекурсия(Дерево.Строки);
КонецПроцедуры
&НаКлиенте
Процедура КосвеныеОбъектов(Команда)
КосвеныеОбъектовНаСервере();
КонецПроцедуры
Объявляем переменную ОбъектыДляПриемки, которая будет видна во всех серверных функциях.
По кнопке с клиента вызываем серверную процедуру, в которой выполняем Запрос с итогами в иерархии. Выгружаем Результат Запроса в Дерево.
с типом обхода ПоГруппировкамСИерархией. Передаем в рекурсивную функцию Строки объекта строительства, который принимаем в эксплуатацию.
Принимаем в эксплуатацию в целом Объект0 (акты КС-11, КС-14), но к учету принимаем объекты самого нижнего уровня – основные средства (Дт01/Кт08.03) документом «Принятие к учету ОС».
Здесь важно – Объект0, это не корневой узел справочника! Но в дереве
он становится корневым (отбор по объекту).
Посмотрим данные дерева в отладчике:
Окно 1: Корень объекта строительства и его строки (Объект0)
Окно 2: Строка корня, нажимаем на ней F2
Окно 3: Строка корня раскрылась и видим Строки
Окно 4: После нажатия F2 на строке Строки
В четвертом окне 4 строки.
Первая строка
Проанализируем этот список (отмечен цифрой 4).
Первая строка – Объект01 – объект, который мы будем принимать к учету (это последний уровень, лист). Эта строка аналог записи в Выборке с типом – ДетальнаяЗапись.
Вторая строка – итоги по объекту Объект0. Эта строка аналог записи в Выборке с типом – ИтогПоИерархии.
Третья и четвертые строки – узлы дерева, их нужно раскрывать рекурсией.
Ниже приведены рекурсивные функции для расчета распределенных косвенных затрат.
&НаСервере
Функция Рекурсия(Строки);
Для каждого Стр Из Строки Цикл
Если Стр.Ссылка = Стр.Родитель.Ссылка Тогда //Итоговая строка
Если НЕ Стр.Родитель = Неопределено И Стр.Ссылка = Стр.Родитель.Ссылка Тогда //Итоговая строка, пропускаем её
ИначеЕсли Стр.Строки.Количество()=1 Тогда // Лист
СтрТЗ=ОбъектыДляПриемки.Добавить();
СтрТЗ.Объект=Стр.Ссылка;
СтрТЗ.Косвенные=0;
Косвенные(СтрТЗ,Стр.Родитель);
Иначе // Узел
Рекурсия(Стр.Строки);
КонецЕсли;
КонецЦикла;
КонецФункции
&НаСервере
Функция Косвенные(СтрТЗ,Родитель)
Если НЕ Родитель = Неопределено Тогда
СтрТЗ.Косвенные = СтрТЗ.Косвенные + СтрТЗ.Объект.Прямые*Родитель.Ссылка.Косвенные/Родитель.Прямые;
Косвенные(СтрТЗ, Родитель.Родитель);
КонецЕсли;
КонецФункции
В функции Рекурсия анализируем, какой тип строки дерева. Для детальной записи количество строк = 1 (своя строка). Для узла количество записей рано количеству потомков +1.
Запросом рассчитали суммарные значения прямых затрат для каждого узла дерева.
Интересная конструкция:
Если НЕ Стр.Родитель = Неопределено И Стр.Ссылка = Стр.Родитель.Ссылка
Во второй части условия проверяется ссылка Родителя, а если он не определён в первой части? Ответ: Если первая часть = Ложь то компилятор в условии И
не проверяет сведущие составляющие условия.
Поставим точку останова в функции КосвеныеОбъектовНаСервере как показано на рисунке ниже:
Увидим результаты запроса.
Так выглядит запись для корневой строки дерева после прохождения рекурсии. Сумма прямых затрат всех объектов нижних уровней равна 12 000.
На прямом пути для элемента самого нижнего уровня создаем строку в таблице значений:
Чтобы увидеть в отладчике ставим точку останове, показанную на рисунке ниже.
И сразу вызываем вторую рекурсивную функцию Косвенные.
Эта функция рассчитывает косвенные расходы для этого объекта от каждого родителя.
В итоге таблица ОбъектыДляПриемки будет выглядеть следующим образом:
Результат соответствует ручному расчету (Листинг 3).
Теперь в цикле для строк этой таблицы можно создавать документы «Принятие к учету ОС».
Но основная цель статьи рассмотреть использование различных областей рекурсивно функции. Перепишем ее следующим образом.
&НаСервере
Функция Рекурсия(Строки);
Для каждого Стр Из Строки Цикл
Если Стр.Строки.Количество()=1 Тогда // Лист
Если НЕ Стр.Ссылка = Стр.Родитель.Ссылка Тогда
СтрТЗ = ОбъектыДляПриемки.Добавить();
СтрТЗ.Объект = Стр.Ссылка;
СтрТЗ.Косвенные = 0;
СтрТЗ.Прямые = Стр.Прямые;
СтрТЗ.Уровень = Стр.Уровень()
КонецЕсли;
Иначе // Узел
Рекурсия(Стр.Строки);
Для каждого СтрОС Из ОбъектыДляПриемки Цикл
Если СтрОС.Объект.ПринадлежитЭлементу(Стр.Ссылка) Тогда
СтрОС.Косвенные = СтрОС.Косвенные + СтрОС.Прямые*Стр.Косвенные/Стр.Прямые;
КонецЕсли;
КонецЦикла;
КонецЕсли;
КонецЦикла;
КонецФункции
Добавим в таблицу ОбъектыДляПриемки колонку Прямые.
В результате расчета получим такую таблицу:
В этом варианте не используется вторая рекурсивная функция на прямом обходе дерева. Рассчитываем необходимые данные на обратном ходе. Конечно
Можно и нужно оптимизировать быстродействие этого решения, но цель здесь другая.
Выводы являются субъективным мнением автора.
Выводы:
-
При разработке алгоритмов с рекурсиями целесообразно использовать параметры функций, для возврата на верхние уровни значений, рассчитанных на нижних уровнях. Или использовать объявление переменных со сквозной видимостью в рекурсиях.
Алгоритмы в этом случае более «прозрачные».
-
Рассматривать целесообразность и использовать обратный ход рекурсивного расчета (область кода после выхода из рекурсивной функции).
