Всем программистам известно, что рекурсии можно избежать при использовании стека.

Например в случае алгоритма обхода выборки по иерархии и выгрузки её в дерево значений это выглядит так:

Выборка = Запрос.Выполнить().Выбрать(ОбходРезультатаЗапроса.ПоГруппировкамСИерархией)
   СтекВызовов = Новый Массив;    
   СтекВызовов.Добавить(Новый Структура("Выборка, Вершины", Результат.Выбрать(ОбходРезультатаЗапроса.ПоГруппировкамСИерархией, "Ссылка"), ТвоеДерево.ПолучитьЭлементы()));
   
   Пока СтекВызовов.Количество() <> 0 Цикл
       ТекущиеПараметры = СтекВызовов[СтекВызовов.Количество()-1];
       Если ТекущиеПараметры.Выборка.Следующий() Тогда
           НоваяВершина = ТекущиеПараметры.Вершины.Добавить();
           ЗаполнитьЗначенияСвойств(НоваяВершина, ТекущиеПараметры.Выборка);
           ДочерняяВыборка = ТекущиеПараметры.Выборка.Выбрать(ОбходРезультатаЗапроса.ПоГруппировкамСИерархией, "Ссылка");
           Если ДочерняяВыборка.Количество() <> 0 Тогда                    
               СтекВызовов.Добавить(Новый Структура("Выборка, Вершины", ДочерняяВыборка, НоваяВершина.ПолучитьЭлементы()));
           КонецЕсли;
       Иначе                
           СтекВызовов.Удалить(СтекВызовов.Количество()-1);
       КонецЕсли;
   КонецЦикла;

А что делать, если коллекция, которая имеет иерархию и в которой невозможно обратиться к элементу по индексу (как в случае дерева значений) или обратиться к следующему элементу (как в примере выше ТекущиеПараметры.Выборка.Следующий()), но возможен обход элементов ТОЛЬКО с помощью конструкции

Для Каждого Элемент Из КоллекцияЭлементов Цикл

КонецЦикла

В примере ниже я имею дело с КоллекцияЭлементовОтбораКомпоновкиДанных (это алгоритм поиска в дереве элемента с определенным идентификатором).

&НаКлиенте
Функция НайтиНастройку(Настройка)
   
   ИД_Настройки = Настройка.ИдентификаторПользовательскойНастройки;
   Для Каждого Элемент Из КомпоновщикНастроек.Настройки.Отбор.Элементы Цикл
       НайденноеЗначение = НайтиРекурсивно(Элемент, ИД_Настройки);
       Если НайденноеЗначение <> Неопределено Тогда
           Возврат НайденноеЗначение;
       КонецЕсли;
   КонецЦикла;
   
КонецФункции

&НаКлиенте
Функция НайтиРекурсивно(ВерхнийЭлемент, ИД_Настройки)
   
   // проверяем сам элемент на равенство
   // идентификатору пользовательской настройки
   Если ВерхнийЭлемент.ИдентификаторПользовательскойНастройки = ИД_Настройки Тогда
       Возврат ВерхнийЭлемент
   Иначе
       // проверяем наличие коллекции подчиненных элементов
       СтруктураПроверки = Новый Структура;
       СтруктураПроверки.Вставить("Элементы");
       ЗаполнитьЗначенияСвойств(СтруктураПроверки, ВерхнийЭлемент);
       
       Если СтруктураПроверки.Элементы = Неопределено Тогда
           Возврат Неопределено;
       КонецЕсли;        
   КонецЕсли;        
   
   // перебираем дочернюю коллекцию
   Для Каждого ПодчиненныйЭлемент Из ВерхнийЭлемент.Элементы Цикл                
       НайденноеЗначение = НайтиРекурсивно(ПодчиненныйЭлемент, ИД_Настройки);
       Если НайденноеЗначение <> Неопределено Тогда
           Возврат НайденноеЗначение;
       КонецЕсли;
   КонецЦикла;
   
   // если ничего не нашли
   // в иерархии ВерхнийЭлемент.Элементы
   // возвращаем НЕОПРЕДЕЛЕНО
   
   Возврат Неопределено;
   
КонецФункции

Здесь иерархический обход необходИм, так как возможна группировка условий по И, НЕ и ИЛИ.

Можно ли реализовать тот-же алгоритм БЕЗ рекурсии и чтоб это было рациональнее с точки зрения производительности ???

(2) С целью повышения производительности.
(4) В том-то и проблема, что ПО ИНДЕКСУ ОБРАТИТЬСЯ НЕЛЬЗЯ.
Можно только этим циклом:
Для Каждого Элемент Из КоллекцияЭлементов Цикл

КонецЦикла

(4) тз - лишняя ТЗ на каждом уровне забьет память похлестче рекурсии

(4) Лучше соотвествие. Но и оно не решит проблемы.

(6) на каком каждом? тз всего одна

(5) индекс в результирующей тз

(8)(9) Вас понял. Но даже если вспомогательная коллекция всего (тз, соответствие - неважно) одна она все равно отъест память хуже рекурсии.

(10)Хм... Или все-таки не всегда???

В общем, будем считать, что копирование исходной коллекции - НЕ выход.

(12) то есть стэк тебя не устраивает?, я говорю не про копирование коллекции, а про выстраивание ее в плоскую структуру, можно некое подобие стека организовать

(13) Стек - отдельный массив, а плоская структура - ещё один.

Кстати пришла идея - а не поможет-ли в такой ситуации динамическое формирование строк программного кода и выполнение последних с помощью команды Выполнить(ТекстКода) - ведь так можно получить цикл неограниченной вложенности. Но опять-же оправдано ли это?

стек = коллекция
выполнить - непроизводительна, и код не совсем удобно читать будет

(15) Аааааааа... В ТЗ ведь можно НЕ добавлять/удалять лишние элементы (уже пройденные вершины). И тогда она будет составлять лишь малую часть от исходной коллекции, я прав?

(16) да, вариантов много

Автор - хвастается, или что?
А нифига не понял...

(18) Никак нет. Просто решил исследовать проблему, с которой сталкиваюсь довольно часто.

+(19) Решение найдено в пунктах (6) - (17)

(19) 10500 мест у тебя, где можно оптимизировать, вместо этого мизера... Что не так? Долго работает?

(5) И прямо много производительности высвободится, да?

(0) отбор по уровню?

Забубенить в Дерево колонку НомерСтроки и по нему искать через

Древо.Строки.НайтиСтроки(СтруктураПоиска,Истина);

Да, кстати, ваш НайтиРекурсивно() вполне заменяется конструкцией (24). Чтите СП!!!

Рекурсия, стэк... pffff. Слов то понапридумывали.

Ааа, там не дерево значений, там КоллекцияЭлементовОтбораКомпоновкиДанных. Ниасилил дочитать, там да, НайтиСтроки() не прокатит.

используйте 8.3 там реализована защита от бесконечной рекурсии(с)

(28) а от деления на ноль там есть защита?

(21)(22) Производительность, конечно, не возрастет. Но исследовательский интерес задачка по-любому должна вызвать. И её рациональное решение тоже.

(29) Она не защищает.. Она реально делит на ноль. Для разработки 8.3 привлекали Чака. 146%

(30) Исследуй пожалуйста, чем исключительная блокировка отличается от разделяемой.. И минимум 1 человек будет тебе благодарен.

v8: УПП 1.3 . Таки нет управляемых блокировок?

(30) имхо, ответ отрицательный
конструкция "Для каждого" фактически создает невидимый для нас объект-итератор
нам нужно неизвестное количество таких объектов
к сожалению их количество должно быть известно на этапе компиляции
всё

(№4) пример кода показать? итераторы ты можешь сохранять

(35) хотелось бы посмотреть

(28)(31) %) (32)Как только руки дойдут - так сразу. (35) Давай - я тоже оценю.

(36) на примере дерева можно, без хаков, естественно)

+(38) это вопрос

(30) Веришь-нет, вообще не вызывает. Код из (0) может и работает на 10, а то и все 20% быстрее обычного, но при этом существенно возрастают затраты на уборщиц, оттирающих взорванные мозги от монитора. Поэтому такие задачи я буду решать рекурсией и не париться. И человек, который откроет мой код после меня, не будет рисковать душевным здоровьем и сразу (ну или почти сразу) поймет, как это все работает.

(38) делай, я не против

(41)    д = Новый ДеревоЗначений;
   д.Колонки.Добавить("Значение");
   Для инд = 0 по 9 Цикл
       д.Строки.Добавить().Значение = "" + инд;
   КонецЦикла;
   
   Для инд = 0 По 9 Цикл
       д.Строки[5].Строки.Добавить().Значение = "5." + инд;
   КонецЦикла;
   
   стек = Новый Массив;
   стек.Добавить(д);
   Пока стек.Количество() > 0 Цикл
       Для каждого строка Из стек[0].Строки Цикл
           Сообщить(строка.Значение);
           Если строка.Строки.Количество() > 0 Тогда
               стек.Добавить(строка);
           КонецЕсли;
       КонецЦикла;
       стек.Удалить(0);
   КонецЦикла

(40) где в (42) взорванные мозги?

(42) Круто. И че с этим потом делать? :)

+(44) И вообще - че оно делает?

вот второй вариант, уже с последовательным обходом, здесь мы просто сохраняем состояние итератора, так как 1с этого за нас не сделает:


   д = Новый ДеревоЗначений;
   д.Колонки.Добавить("Значение");
   Для инд = 0 по 9 Цикл
       д.Строки.Добавить().Значение = "" + инд;
   КонецЦикла;
   
   Для инд = 0 По 9 Цикл
       д.Строки[5].Строки.Добавить().Значение = "5." + инд;
   КонецЦикла;
   
   Для инд = 0 По 9 Цикл
       д.Строки[5].Строки[3].Строки.Добавить().Значение = "5.3." + инд;
   КонецЦикла;
   

   стек = Новый Массив;
   стек.Добавить(д);
   Пока стек.Количество() > 0 Цикл
       Для каждого строка Из стек[0].Строки Цикл
           Сообщить(строка.Значение);
           Если строка.Строки.Количество() > 0 Тогда
               стек.Добавить(строка);
           КонецЕсли;
       КонецЦикла;
       стек.Удалить(0);
   КонецЦикла;
   
// здесь последовательно
   стек.Добавить(д);
   Пока стек.Количество() > 0 Цикл
       нашлиВетку = Ложь;
       Для каждого строка Из стек[0].Строки Цикл
           Если нашлиВетку Тогда
               стек[2].Строки.Добавить(строка);
           Иначе
               Сообщить(строка.Значение);
               Если строка.Строки.Количество() > 0 Тогда
                   стек.Вставить(1, строка);
                   стек.Вставить(2, Новый Структура("Строки", Новый Массив));
                   нашлиВетку = Истина;
               КонецЕсли;
           КонецЕсли;
       КонецЦикла;
       стек.Удалить(0);
   КонецЦикла

(45) эито обход дерева без рекурсии

(47) Мда.

Ага... Тут (42) программа дальше не пойдёт, пока не будут пройдены строки одного уровня. Вот это (42) надо-бы покрасивее оформить - и в книгу знаний.

// В итоге эта рекурсивная функция:

&НаКлиенте
Функция НайтиРекурсивно(ВерхнийЭлемент, ИД_Настройки)
 
  Если ВерхнийЭлемент.ИдентификаторПользовательскойНастройки = ИД_Настройки Тогда
      Возврат ВерхнийЭлемент
  Иначе
      СтруктураПроверки = Новый Структура;
      СтруктураПроверки.Вставить("Элементы");
      ЗаполнитьЗначенияСвойств(СтруктураПроверки, ВерхнийЭлемент);
     
      Если СтруктураПроверки.Элементы = Неопределено Тогда
          Возврат Неопределено;
      КонецЕсли;        
  КонецЕсли;        
 
  Для Каждого ПодчиненныйЭлемент Из ВерхнийЭлемент.Элементы Цикл                
      НайденноеЗначение = НайтиРекурсивно(ПодчиненныйЭлемент, ИД_Настройки);
      Если НайденноеЗначение <> Неопределено Тогда
          Возврат НайденноеЗначение;
      КонецЕсли;
  КонецЦикла;
 
  Возврат Неопределено;
 
КонецФункции

//после преобразования стала такой:

&НаКлиенте
Функция НайтиРекурсивно(ВерхнийЭлемент, ИД_Настройки)
   
   Стек = Новый Массив;
   Стек.Добавить(ВерхнийЭлемент);
   
   Проверка = Новый Структура;
   
   Пока Стек.Количество() <> 0 Цикл
       Если Стек[0].ИдентификаторПользовательскойНастройки = ИД_Настройки Тогда
           Возврат Стек[0];
       Иначе
           Проверка.Вставить("Элементы", Неопределено);
           ЗаполнитьЗначенияСвойств(Проверка, Стек[0]);    
           Если ЗначениеЗаполнено(Проверка.Элементы) Тогда
               Для Каждого ПодчиненныйЭлемент Из Стек[0].Элементы Цикл
                   Стек.Добавить(ПодчиненныйЭлемент);
               КонецЦикла;
           КонецЕсли;
       КонецЕсли;
       Стек.Удалить(0);
   КонецЦикла;
   
   Возврат Неопределено;
   
КонецФункции

Всем спасибо, особенно izekia.

(42) Вообще, по-моему, это называется "Поиск в ширину". И массив там уже используется скорее не в качестве стека, где можно в один конец добавлять/удалять, а в качестве другой коллекции - ДЕКа, где можно манипулировать с обоими концами коллекции.

(49) лучше (46) там оба варианта

(51) Ага, а (46) - это уже обход "вглубь".

клево

(53) Я знал что тебе понравится.

(46) Второй вариант, конечно, красив, но память он будет жрать побольше первого. Он по крайней мере по-дерева в стек засунет - это уже не дело (((.

>по-дерева
полдерева

(0) Автора забанить! он покусился на святое чувство одноэсников - чувство полноценности.

Рекурсия с точки зрения хранения промежуточных данных ииспользут стек.
А вот wiki:Хвостовая_рекурсия

хвостовая рекурсия

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

[править] Применение

Хвостовая рекурсия часто применяется в программах на функциональных языках программирования. Многие вычисления на таких языках естественно выражать в виде рекурсивных функций, а возможность автоматической замены транслятором хвостовой рекурсии на итерацию означает, что по вычислительной эффективности она равна эквивалентному коду, записанному в итеративном виде.

Создатели функционального языка Scheme, одного из диалектов Lisp, оценили важность хвостовой рекурсии настолько, что в спецификации языка предписали каждому транслятору этого языка в обязательном порядке реализовывать оптимизацию хвостовой рекурсии.[2]

(56) все совсем не так плохо, можешь сам посчитать сколько максимально элементов там может оказаться, опять же смотря как все это обрабатывать

(0) а вы в курсе, что рекурсия использует стек?

(58) хвостовая рекурсия преобразуется в цикл, это как пример с вчерашним фибоначчи
а = 0;
б = 1;
Для инд = 2 По номерЧисла Цикл
   б = б + а;
   а = б - а;
КонецЦикла;

в итоге необходимое число в б

(60) кто тебе такое сказал?

(60) Тут вопрос в другом: "Как это сделать не используя обращение подпрограмм самих к себе в рамках 1С в случае, когда для иерархической коллекция для перебора элементов определен только цикл Для Каждого Из... ?". Ни индексов, ни открытого итератора - ничего нету.

Можно считать, что вопрос "Как обойти такую иерархию?" закрыт в (42). Поиск "в ширину" (42) работает неплохо. Но вот вопрос "Как обойти такую иерархию именно В ГЛУБИНУ?" без засорения оперативной памяти компьютера больше, чем посредством обращения подпрограмм самих к себе (рекурсией), пока открыт.

(61) http://algolist.manual.ru/ds/basic/stack_recursion.php

Так же смотри файберы wiki:%CF%EE%F2%EE%EA_%E2%FB%EF%EE%EB%ED%E5%ED%E8%FF

которые раньше часто использовались в том числе и для рекурсивного обхода деревьев смотри yield
http://habrahabr.ru/post/116124/

Но в нет сейчас пошли по пути создания классов и хранение в них состояния
http://www.rsdn.ru/article/csharp/CSharp_Iterators.xml#EOAAC

(65) это к чему?

(66) Это к 62

(67) сарказм, просто всю тему обсуждали как сделать это без рекурсии, и тут внезапно вылез этот перец и вставил свою гениальную фразу

(67) (68) Стоп-стоп-стоп... Ветка поросла вкривь.
Мы отклонились от исходной темы.

Итак: мы изначально решали проблемы, описанные в (64). Все мы прекрасно знаем, что рекурсия, так или иначе, использует стек (программно, или аппаратно) - для нас это не открытая Америка. Открытый вопрос в (64).

(68) Сарказм в том, что в 1С для многих вещей не хватает нетовских итераторов (yield). Про Linq (которые кстати и используют итераторы и ленивые вычисления) вообще промолчу.

(64) Да не открыт. Читай 65. Тебе нужно делать автомат с сохранением состояния Дереве перемещаясь по нему в зависимости от его состояния и запоминая предыдущее. Так работают нетовские классы. Можешь посмотреть как реализовано у меня B+ деревья
http://rsdn.ru/article/alg/tlsd.xml
http://1c.proclub.ru/modules/mydownloads/personal.php?cid=115&lid=2019

А я и не знал что рекурсии надо избегать и избегать ее надо с помощью стэка.

(70) Открыт. Да, в (46) обход "вглубь" без рекурсии СРЕДСТВАМИ 1С сделан, но такой способ менее оптимален, чем классическая рекурсия. Там по сути, как только найден элемент с ветвями все элементы после него по очереди сохраняются в массив, чтобы "запомнить" состояния, которые осталось пройти. А там может быть 1/2, а то и 9/10 дерева и все это пихается в ещё один массив. Ясно, что такой способ в плане производительности слабее классической рекурсии.

(72) Тебе обязательно стек. Очередь/дек не подойдёт?

(73) в (42) очередь и используется

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

(73) Подойдёт, конечно. Но как это сделать с помощью них? Ещё раз повторюсь: особенно интересен РАЦИОНАЛЬНЫЙ обход "в глубину", "в ширину" описан в (42) (кстати, там дек).

(74) Ну дык ТС продолжает интересоваться...

(72) Нет тебе нужно хранить тольк путь от корня к текущему листу, что бы подняться по дереву.
Если дерево у тебя вырождено то будет такая ситуация
Так же хранять данные и в стеке при рекурсии. Посмотри на рекурсию с точки зрения хранения данных и тебе все станет ясно.

(76) Именно. И тут вряд ли чего нового выдумаешь - по сравнению с классикой. В (42) - IMHO, ответ.

(72) ну невозможность легко доказывается
мы не можем сохранить состояния такого итератора, соответственно если последовательность обработки значений критична, то необходимо сохранять в стек оставшиеся элементы необработанного итератора
в 1С вариантов больше нет

(78) В случае с деревом или с иерархической выборкой проблем нет, но что делать, если прямого позиционирования нет и есть только встроенный итератор, как, например, для (0) - там КоллекцияЭлементовОтбораКомпоновкиДанных

(81) я не использовал прямого позиционирования, просто мне проще было использовать дерево в качестве тестового примера, а сам метод универсальный

(82) Это я понял.

(77) оффтоп: посмотрел вчера на фшарп, что-то синтаксис не очень порадовал, далеко ему до лаконичности хаскелла, с другой стороны много вкусного из нета

(81) Самый смех заключается в том, что внутри любого итератора в недрах существует MoveNext.
Но в таких случаях только копирование в массив массивов или рекурсивный обход. А вот чем тебе рекурсия то не угодила? Кстати самый быстрый обход данных если тебе не нужны останвливаться и сохранять состояние
(84) Тогда тебе нужно смотреть в сторону Немерле.

(84) Практически все функциональное программирование построено на рекурсии и живут и радуются.
Главное что бы размер программного стека не переполнялся

(86) это к 81

(85) ну доберусь, просто не хочется разбрасываться Хаскелла пока хватает)

(86) визуально - да, но чаще всего код пишется так, чтобы компилятор разглядел там хвостовую рекурсию и соптимизировал
то есть в конечной программе рекурсии нет

(84) OFF: F# - это *ML. Несколько иной подход (но тем не менее - вполне последовательный). Сравнивать с Haskell - смысла, IMHO, нет - те же яйца, только в профиль. Плюс - действительно неплохая интероперабельность (насчёт .NET).

(85) Nemerle - это особь статья. Если Haskell - чисто функциональный язык, Nemerle - гибрид + уникальнейшие макросредства.

(90) хаскел чисто функциональный, фшарп - грязный, если так можно сказать ... немного красота и выразительность теряется

(85) Да всем мне рекурсия угодила. Просто, так сказать, научный интерес к нестандартным задачам. Сколько видел иерархий - все обходятся стеками/деками/очередями, а такие как в (81) - ни в какую.

(92) Не "грязный". Другая ветка - *ML. Сочетание ООП с функциональным программированием (на мой взгляд, довольно аккуратное, хотя тут имеется пара мыслишек - но их пока рано высказывать :-)
Всё необходимое для ФП имеется (и есть возможности писать чисто ФП) - но приближенно к практике.
Те же монады в Haskell - красивы теоретически, но на практике всё равно приходится отождествлять их с "объектами" (а мыслить исключительно в терминах ФП - оно, конечно, можно... но не стоит доводить каждую идею до абсур^W логического завершения :-).

+(94) В прошлой ветке я привёл предельно неудачно-крайний пример - но он прекрасно иллюстрирует суть, IMHO.

(92) Ну на то он и гибридный. Хочешь ФП хочешь императив. Для каждой задачи свой подход.
И соответственно мутабельные и иммутабельные структуры. ООП при всем очень могучий механизм.
Да и мыслить постоянно рекурсивно тяжело решая широкий круг задач.
Зато в с# есть Linq в том числе и 2SQL

(96) +1

(96) Интересно, эти "радости" появятся в платформе 1С??? А то работать с оперативной памятью, как с SQL-таблицами нельзя, класс для создания объекта можно создать разве что запихав методы и свойства в обработку-объект (только инкапсуляцию можно реализовать, ни наследования, ни полиморфизма, ни перегрузки операторов).

(98) Это вряд ли - насчёт "появятся". Да и не хрен им в платформе 1С делать.

100.

(94)(96) "грязный" - это не значит плохой, я хаскеллом занимаюсь в качестве хобби и он мне именно своей чистотой нравится и именно этого я не увидел в F#

(99) Вообщето очень часто нужно разного рода фильтры к ТаблицеЗначений применять. Использовать для этого циклы или временные таблицы с SQL как то не кшерно. В той же нетовской DataTable любые фильтры ввиде текста в том числе и для DataView можно строить динамические фильтры. Часто пользуюсь очень удобно

(102) Ну подожди 8.4. Вдруг да реализуют :-)
(Понятно, что .NET помощнее 1С будет в общем случае).

(103) Да им давно нужно сделать язык под Net. И не будет никаких проблем с их недоязыком. Можно использовать все библиотеки net и ООП.