gifts2017

Мастер класс «O-Planet»: использование рекурсивных вычислений в 1С

Опубликовал Олег Пономаренко (O-Planet) в раздел Программирование - Практика программирования

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

Автор, приведя минимум теории, рассматривает на простом примере, как можно формализовать задачу, чтобы в ее решении можно было применить рекурсивные методы
Из курса программирования известно, что рекурсией называется вызов функцией самой себя. Фактически, рекурсия является первым шагом к логическому программированию, потому что грамотное ее использование позволяет составить алгоритм, не решая задачи окончательно.

Как решить задачу рекурсивно? Запомним простую аксиому: задачу, имеющую рекурсивное решение, всегда можно сформулировать индуктивно. Покажу это на простом примере. Допустим, мы ищем путь из точки А в точку В в лабиринте. Мы оказались на очередном перепутье. Перед нами несколько направлений возможного пути. Что будет, если мы выберем одно из направлений? Правильно, мы окажемся на следующем этапе-перепутье, опять с несколькими направлениями, и вновь перед нами встанет задача выбора. Когда же в некоторый момент мы заходим в тупик или в точку, в которой уже были ранее, нам необходимо просто возвратиться на шаг назад и выбрать другое направление пути из возможных. И так до тех пор, пока мы не придем в конечную точку. Таким образом, сложная задача поиска пути в лабиринте была сведена к однотипным операциям выбора в каждой очередной его точке. Алгоритм рекурсивного решения этой задачи будет выглядеть примерно так:

Функция ПоискПути(Х)
	Если Х=А Тогда
		Возврат 1; // Конец пути достигнут здесь
	КонецЕсли;
	Пока Есть_Возможные_Пути(Х)=1 Цикл
		У=Очередная_Точка(Х); 
		Если ПоискПути(У)=1 Тогда 
			Возврат 1; // Конец пути был достигнут где-то там
		КонецЕсли;
	КонецЦикла;
	Возврат 0; // Тупик, или не осталось вариантов
КонецФункции


Но вернемся к теме 1С. Неужели рекурсию можно использовать и здесь успешно, спросит дока? Надо отметить, что у большинства рекурсивных алгоритмов есть существенный недостаток: они ресурсоемки и достаточно медленны по сравнению с обычными циклами, поэтому, вопрос звучит вполне уместно. Без сомнения, приведенный пример можно решить и не прибегая к рекурсивным вызовам. Но иногда без них бывает почти не обойтись.

Рассмотрим задачу, решение которой для отдельных бухгалтеров может стать исполнением одного из их заветных желаний. Попробуем привязать долги покупателей к конкретным расходным накладным в программе 1С:Бухгалтерия 7.7. Без сомнения, решить эту задачу в лоб – означает, пересчитать всю базу с начала времен, ведь каждый контрагент, собственно говоря, может что-то покупать, потом частично это оплачивать, потом покупать что-то еще и т.д.

Будем решать эту задачу в обратном направлении. Вспомним, что метод FIFO, вообще говоря, должен распространяться и на оплату. Иными словами, если от какого-то клиента поступает оплата, то ни что не мешает нам привязать ее к самому раннему неоплаченному документу по этому клиенту. Итак, если клиент А должен нам 1000 рублей, то можно с уверенностью считать неоплаченными последние N документов, по которым он что–либо у нас приобрел на сумму, не меньше, чем 1000 рублей.

Что ж, будем перебирать все операции по контрагентам в обратном порядке, разнося по ним сумму имеющегося долга. Разумеется, это было бы быстрее, чем перебирать и пересчитывать все документы с начала. Построим рекурсивную обработку операций. Будем рассматривать операции отрезками в 31 день.

Функция ПолучитьДокументы(Контрагент,Т,Знач Д1,Знач Д2,СальдоКон=0)
// Т – таблица значений, которая заполняется документами на выходе рекурсии
// Д1 и Д2 – очередной рассматриваемый период
// СальдоКон – сальдо по контрагенту на конец периода. Значение в 
// самом начале равно нулю. В дальнейшем оно будет расчитано


Составим запрос по операциям контрагента за месяц

	Ит=СоздатьОбъект("БухгалтерскиеИтоги");
	Ит.ИспользоватьСубконто(ВидыСубконто.Контрагенты,Контрагент,2,0);
	Если Ит.ВыполнитьЗапрос(Д1,Д2,"62.1",,,1,"операция","С")=0 Тогда
		Сообщить("Ошибка!");
		Возврат 0;
	КонецЕсли;


Определим условие завершения рекурсии

	Если СальдоКон=0 Тогда
		СальдоКон=Ит.СКД("С")-Ит.СКК("С");
	КонецЕсли;
	Если СальдоКон<=0 Тогда
		Возврат 1; 
	КонецЕсли;


Нам понадобится вспомогательная таблица значений

	Таб=СоздатьОбъект("ТаблицаЗначений");
	Таб.НоваяКолонка("Приход","Число",15,2);
	Таб.НоваяКолонка("Дата","Дата");
	Таб.НоваяКолонка("Позиция");
	Таб.НоваяКолонка("Документ","Документ");


Заполним таблицу найденными в запросе операциями

	Ит.ВыбратьПериоды(); 
	Пока Ит.ПолучитьПериод()=1 Цикл
		Таб.НоваяСтрока();
		Таб.Приход=Ит.ДО("С");
		Таб.Документ=Ит.Операция.Документ;
		Таб.Дата=Ит.Операция.Документ.ДатаДок;
		Таб.Позиция=Ит.Операция.Документ.ПолучитьПозицию();
	КонецЦикла;


Если в текущем месяце не было докуменетов, то рассмотрим месяц ранее по рекурсии. Это будет косвенное условие завершения.

	Если Таб.КоличествоСтрок()=0 Тогда
		Возврат ПолучитьДокументы(Контрагент,Т,Д1-31,Д1-1,СальдоКон);
	КонецЕсли;


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

	Таб.Сортировать("-Позиция");


Разнесем долг контрагента по документам, формирующим этот долг. В тот момент, когда остаток долга станет меньше нуля, будем считать, что долг полностью привязан к документам.

	Таб.ВыбратьСтроки();
	Пока (Таб.ПолучитьСтроку()=1)и(СальдоКон>0) Цикл
		Если Таб.Приход>0 Тогда
			Т.НоваяСтрока();
			Т.Документ=Таб.Документ;
			Т.Дата=Таб.Дата;
			Т.Долг=Таб.Приход;
			Т.ОстатокДолга=СальдоКон;
			СальдоКон=СальдоКон-Таб.Приход;
		КонецЕсли;	
	КонецЦикла;


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

	Если СальдоКон>0 Тогда
		Возврат ПолучитьДокументы(Контрагент,Т,Д1-31,Д1-1,СальдоКон);
	КонецЕсли;


Если покрыли, то возвращаем 1

	Возврат 1;
КонецФункции


Думаю, теперь каждый без труда поймет, как использовать эту функцию в основном расчетном модуле. Приведу примерный, упрощенный вариант.

Таблица=СоздатьОбъект(«Таблица»);
Таблица.ВывестиСекцию(«Шапка»);

Т=СоздатьОбъект(«ТаблицаЗначений»);
Т.НоваяКолонка(«Документ»);
Т.НоваяКолонка(«Дата»);
Т.НоваяКолонка(«Долг»);
Т.НоваяКолонка(«ОстатокДолга»);

Контрагенты=СоздатьОбъект(«Справочник.Контрагенты»);
Контрагенты.ВыбратьЭлементы();
Пока Контрагенты.ПолучитьЭлемент()=1 Цикл
	Д=РабочаяДата();
	Т.УдалитьСтроки();
	ПолучитьДокументы(Контрагенты.ТекущийЭлемент(),Т,Д-30,Д);
	ВывестиВТаблицу(Таблица,Контрагенты.ТекущийЭлемент(),Т);
КонецЦикла;

Таблица.ВывестиСекцию(«Подвал»);
Таблица.Опции(0,0,0,0,«ДолгиКонтрагентов1»,«ДолгиКонтрагентов2»);
Таблица.ТольоПросмотр(1);
Таблица.Показать(«Долги»);


Мы рассмотрели упрощенный вариант задачи, предполагая применение метода FIFO к оплате, и как видите, рекурсия в приведенном случае вполне оправдана. Без сомнения, больший интерес представляет алгоритм, в котором учитывается как дебетовые, так и кредитовые обороты по счету 62, и в этом случае, на выходе мы можем получить что-то вроде книги покупок, но без применения забалансовых счетов. Что ж, дерзайте, коллеги!

Приведенный алгоритм применен в наших обработках "Кто нам должен" и "Кому мы должны"

Подробнее с бесплатными и коммерческими решениями партнерства O-Planet можно ознакомиться на сайте партнерства и через салон продаж «Белка»: Бизнес Электроника http://www.belkamag.ru


См. также

Подписаться Добавить вознаграждение

Комментарии

1. Олег Пономаренко (O-Planet) 06.08.06 20:55
Читаем, и рейтинг плюсуем!
2. Олег Пономаренко (O-Planet) 06.08.06 20:58
... если оно того стоит, конечно :-) (Вот я и узнаю)
3. Сhe Burashka (CheBurator) 06.08.06 21:28
нормально...
только бы оценить оправданность применения рекурсии с точки зрения затрат на вызовы и возвраты из функций...
4. VasilyKushnir (vasilykushnir) 07.08.06 14:28
+1
Che, ИМХО иногда простота программирования и ясность кода с лихвой окупают миллисекундное увеличение работы процедуры.
Молодец O-Planet (чувствуется, что программировал не только на 1С). Кстати, у меня на днях тоже руки чесались запузырить рекурсию (вспомнить молодость), но когда оценил трезво (и это после выходных) алгоритм, то решил, что для отработки функции максимум три раза не стоит разводить бодягу.
5. Сhe Burashka (CheBurator) 07.08.06 18:30
Василию: ну так и я про то же...
но при больших количествах рекурсии: это же надо все запоминать и пр. - насколько это накладно?
О-планет - молодец, не дает расслабляться, все время интересные публикует...
6. Александр Орефков (orefkov) 08.08.06 11:41
Имхо пример не совсем удачный. Здесь невооруженным глазом видна хвостовая рекурсия, легко преобразуемая в "Пока СальдоКон > 0 Цикл".
Рекурсивные процедуры очень хорошо и оправдано подходят для задач, связанных с обработкой древовидных данных.
При этом практически все рекурсии могут быть преобразованы в цикл + некий стек, который с помощью таких типов как "СписокЗначений" и "ТаблицаЗначений" довольно просто реализуется.
7. Олег Пономаренко (O-Planet) 09.08.06 16:31
Он не то чтобы неудачный. Он простой и понятный. И прекрасно, что видно "невооруженным глазом" Плохо, когда в примере ничего не видно.
8. Александр Орефков (orefkov) 10.08.06 15:59
И как тогда это соотносится с "рекурсия в приведенном случае вполне оправдана"?
Для чего этот пример? Ознакомить всех с тем, что в 1С есть рекурсия, на простом и понятном примере?
Ну так хватило бы факториала.

А здесь наоборот - вредная рекурсия. Допустим придется обрабатывать 10 месяцев.
10 вложенных вызовов, в каждом из которых свой экземпляр Таб и ИТ, которые кушают память, пока
все 10 вызовов не отработают.
А сделай это в цикле - при переходе к предыдущему периоду повторно используются теже экземпляры Таб и Ит.
Понятно конечно, что 1Сник память не считает, но все же...
9. Олег Пономаренко (O-Planet) 10.08.06 16:23
Ты веселый парень! Читай внимательно:

> Автор, приведя минимум теории, рассматривает на простом примере, как можно
> формализовать задачу, чтобы в ее решении можно было применить рекурсивные методы

Я, скажи, задачу выполнил? Пример простой и понятный? Задача формализована под рекурсию или нет? Смысл учебной статьи как раз и заключается в приведении простых примеров из предметной области, а не всяких там факториалов. Человек умный скажет "ух, блин!", чуть что-то переделает под себя, и это будет уже серьезно! Потом, я предупреждал, что рекурсия - это всегда ресурсоемкий ход.

Кстати, по поводу остаточной рекурсии... Она получается, как минимум, тройным циклом. Это есть гуд? Так что, мой пример отличный и в тему.
10. Олег Пономаренко (O-Planet) 10.08.06 16:28
> 10 вложенных вызовов, в каждом из которых свой экземпляр Таб и ИТ, которые кушают память, пока
все 10 вызовов не отработают.
А это стиль программирования под винды вообще... Посмотри дельфи, на пример. Там часто приходится встречать, когда что-то переносится в процедуре в TStrings, потом обрабатывается в памяти, хотя можно было бы обойтись простым циклом. Такой ход и в типовых конфигурациях 1С встречается частенько. Память на то и существует, чтобы ее использовать. Процесс в памяти - быстрее процесса в цикле
11. Александр Орефков (orefkov) 10.08.06 17:12
Да ради бога, если ты ставил себе цель "Формализовать задачу под рекурсию", то справился блестяще. Любой цикл можно формализовать под рекурсию.
Я просто размышлял нат твоей фразой "рекурсия в приведенном случае вполне оправдана"
12. Алексей Л (lalex23) 10.08.06 21:30
Поделюсь, мне рекурсия в 1С понадобилась несколько раз, помню только последний: кто видел в УПП конструктор спецификаций тот поймёт - сложное изделие разворачивается до самых мелких деталек.
Потому поддержу orefkov-а: наиболее полезно пользовать рекурсию для ДРЕВОВИДНЫХ структур, рассчётов чего либо типа факториала
13. Олег Пономаренко (O-Planet) 10.08.06 23:59
> Я просто размышлял нат твоей фразой "рекурсия в приведенном случае вполне оправдана"
Отчет получился простым достаточно и быстрым. Можешь проверить
14. AlexQC (alexqc) 17.08.06 13:48
to latex23
Факториал кстати, тоже весьма неплохо в цикл разворачивается. Это на самом деле тот же хвост, просто почему-то в классику как пример рекурсии вошел. Есть ИМХО более "рекурсивный" пример - числа Фиббоначи.

to O-Planet.
Ваш пример действительно не совсем к рекурсивному решению подходит - тут на этапе формулировки задачи ("долг по неоплаченным расходным") сразу идет: неоплаченные расходные - последние. Т.е. обратный цикл сам собой и лезет.
Если бы задача продемонстрировать рекурсию в 1С стояла у меня - я бы выбрал обход группировок запроса, с заранее (на этапе программирования) неизвестным к-вом группировок.
15. Олег Пономаренко (O-Planet) 18.08.06 02:00
> Ваш пример действительно не совсем к рекурсивному решению подходит
Может быть. Вообще, использование рекурсии - это дело выбора, не более того. У нас даже теорема в свое время по курсу теоретической информатики была о том, что любая рекурсия может быть алгоритмически представлена вложенными циклами.
16. Олег Чалаев (OlegTor) 18.08.06 10:56
Лично я при делеме использовать или нет рекурсию руководствуюсь следующими правилом.
Использовать рекурсию нужно в следующих случаях:

1. Задача не может быть решена при помощи нерекурсивного алгоритма.
2. Нерекурсивный алгоритм громоздкий и запутанный.
3. Используются рекурсивные структуры данных.
17. Олег Пономаренко (O-Planet) 18.08.06 11:14
По поводу 1: ЛЮБАЯ рекурсивная задача может быть решена с помощью нерекурсивного алгоритма...
18. Олег Чалаев (OlegTor) 18.08.06 11:37
А если решение задачи претендует на универсальность, и количество вложенных циклов и структура их вложенности неизвестна?
19. AlexQC (alexqc) 18.08.06 14:52
Не совсем любая. Чтобы рекурсия сводилась к итерационной системе, она должна быть либо "хвостовой", либо приводиться к хвостовой, либо иметь ограниченную (на этапе построения алгоритма) максимальную глубину. Остальные в общем случае в итерацию не разворачиваются (не считая изврата с "эмуляцией" рекурсии).
20. Олег Пономаренко (O-Planet) 18.08.06 15:16
> не считая изврата с "эмуляцией" рекурсии
Об этом-то и речь! Почему, собственно, изврат? Эмуляцию можно извратно реализовать - это факт, но иногда эмуляция рекурсии становится самостоятельным и достаточно оптимальным алгоритмом. Я помню делал когда-то на С++ класс TPredicat по типу прологовского. Так вместо рекурсии я делал стек, в котором хранил все локальные данные на определенном уровне обхода списка предикатов, а сами предикаты просто ссылались на свою ячейку этого стека. Фактически, эмуляция рекурсии. Но именно эта эмуляция делала работу быстрее.

21. AlexQC (alexqc) 23.08.06 11:20
Изврат - потому что это по-сути - все равно рекурсивноге решение. Разница в том, что стек (со всеми записями-чтениями из него) делается явно тобой, вместо того чтобы поручить эту работу компилятору. Вместо вызова ф-ции используется некое "состояние", которое наверняка тоже сохраняется в стеке. И чем это лучше рекурсии??? ИМХО, больше смахивает на фанатизм - "только бы не рекурсией".

Скажу еще раз - чтобы рекурсия переводилась в итерацию, надо либо чтобы она была хвостовой или сводимой к хвосту - тогда можно делать итерации, идя с конца и накапливая результат. Либо чтобы она имела известную глубину - тогда можно идти сначала, сохраняя промежуточные итоги. В остальных случаях - решение всегда рекурсивно, даже если оформлено как бесконечный цикл :).

А если у вас эмуляция рекурсии получилась быстрее самой рекурсии - значит, рекурсивный алгоритм не был оптимизирован, а при переводе в итерацию вы его оптимизировали, не заметив.
22. AlexQC (alexqc) 28.08.06 14:59
> Нет. Механизм рекурсии реализуется с помощью стека состояний в базовом классе.

Ну так мы и вернулись к тому, с чего начали. Вместо явной рекурсии (вызов ф-ции самой собой) имеем рекурсию неявную ("вызов" состоянием нового состояния, с сохранением предыдущих).
23. Олег Пономаренко (O-Planet) 24.08.06 00:22
> И чем это лучше рекурсии???
Тем, что реализована на классах, на пример. Почему бы возможность рекурсивности обхода не заложить в базовый класс, соответственно, и формирование стека и возможность указать у потомков, что стековать. Согласись, что теперь это уже звучит не как изврат, а как прогрессивный алгоритмический метод, который может быть в разы быстрее и экономичнее рекурсии. На таком подходе вообще можно новый язык программирования предложить спокойно и дисер защитить.
24. AlexQC (alexqc) 24.08.06 14:13
Хм, классы-то тут каким боком??? Может мы о разном говорим?
Если вы рекурсию на классах реализуете - то это всего лишь вопрос реализации; но судя по "новому языку" - имеется в виду рекурсивное определение класса? Тогда советую обратить внимание на функциональное (декларативное) программирование.
25. Олег Пономаренко (O-Planet) 27.08.06 00:29
Я и говорю, что это, в общем, тема диссертации :)
26. Олег Пономаренко (O-Planet) 27.08.06 00:33
> имеется в виду рекурсивное определение класса?
Нет. Механизм рекурсии реализуется с помощью стека состояний в базовом классе.
27. Олег Пономаренко (O-Planet) 28.08.06 22:00
Да. Но тут-то фишка в другом совсем. Мы не используем механизм рекурсивных функций. (А я ренкурсию рассматривал именно в контексте функций) И это очень важный факт, потому что одно - функция работающая рекурсивно, постоянно дергающая программный стек, который однажды просто подвисает, а если и не это, то подвешивает других. Другое - при умелой реализации базового класса с механизмом сохранения и восстановления состояний, мы сами определяем, что сохранять и где, то есть, сами управляем памятью и используем собственный механизм "сбора хвостов". А это - и оптимальность, и скорость.
28. Станислав (zalst) 30.03.07 15:10
мое скромное имхо: отличная статья + великолепный пример!

не считаю что этот пример должен быть ГИГА-полезен! это ж пример! а зачем вам, ваша фантазия и навыки?!!!
+1
29. Alex A (daddy-don) 12.12.10 14:04
Я 7-ки не знаю, можно как-то попроще объяснить пример с субконто и долгами?
Раз уж тема называется "Использование рекурсивных вычислений в 1С" ( а не, скажем, "Задолженость по контрагентам через Рекурсию в 1С 7.7"), и это пример именно рекурсии, а не конкретной узкой реализации - он не должен быть завязан на платформе, а декларировать общие принципы и давать ясное понятие любому.
Вот что такое делает
"СальдоКон=Ит.СКД("С") - Ит.СКК("С");" ??
Для написания сообщения необходимо авторизоваться
Прикрепить файл
Дополнительные параметры ответа