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

06.08.06

Разработка - Математика и алгоритмы

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

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

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

Функция ПоискПути(Х)
	Если Х=А Тогда
		Возврат 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


См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1753    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4415    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7454    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7852    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

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

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4444    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8832    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

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

31.08.2021    7797    dusha0020    8    

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

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

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

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

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

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

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

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

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

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

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

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