Рекурсия в 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    4531    dsdred    53    

72

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

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

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

24.01.2024    5294    YA_418728146    25    

63

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

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

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

11.12.2023    6410    dsdred    36    

112

1С-ная магия

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

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

06.10.2023    18475    SeiOkami    46    

118

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

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

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

14.09.2023    12088    human_new    27    

74

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

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

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

28.08.2023    8822    YA_418728146    6    

141

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

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

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

20.08.2023    6279    sebekerga    54    

94

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

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

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

27.06.2023    15986    SeiOkami    31    

103
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. sound 535 30.06.09 14:27 Сейчас в теме
однозначно чтобы понять рекурсию, надо понять рекурсию
pilotfitz; G_112708749323588293243; alsegor; Yan_Malyakov; th3_mexanic; AhanSere; imxored; denis_aka_wolf; Mi4man; charushkin; BigMih; igor_gk; +12 Ответить
3. venger 2121 30.06.09 14:37 Сейчас в теме
(1) Это поможет:-))) http://infostart.ru/projects/4618/
Но, как доказано где-то когда-то и вроде как математически, любую задачу решаемую рекурсивно, можно решить итеративно и наоборот. Причем в 1С, уж в семерке так точно, рекурсия более затратна, чем цикл:-)
З.Ы. Ниче против статьи и ее автора не имею, просто ремарка:-)
5. Арчибальд 2706 30.06.09 15:01 Сейчас в теме
(3)>Но, как доказано где-то когда-то и вроде как математически, любую задачу решаемую рекурсивно, можно решить итеративно и наоборот.

Вот и скелет доказательства:
f(n+1)=g(f(n))
означает просто
f(n+1)=g(g(g(......g(1)....)
что реализуется циклом
f=g(1);
for i=1 to n loop
f=g(f);
endloop

И далее индукция по n...
6. Evg-Lylyk 4559 30.06.09 15:17 Сейчас в теме
(3) рекурсия более понятна. На счет затратно сомневаюсь :). Хотелось бы увидеть замену рекурсии для варианта автора.
7. venger 2121 30.06.09 15:21 Сейчас в теме
(6) Замерь две функции из первого поста отсюда: http://infostart.ru/forum/forum9/topic9906/messages/
И убедишься.
8. Evg-Lylyk 4559 30.06.09 15:22 Сейчас в теме
(7) что на счет примера автора
9. venger 2121 30.06.09 15:28 Сейчас в теме
(8) Что насчет замера? Какие результаты, в семерке, в восьмерке?
11. Evg-Lylyk 4559 30.06.09 15:31 Сейчас в теме
(9) Так можно увидеть вариант автора без рекурсии
10. Evg-Lylyk 4559 30.06.09 15:30 Сейчас в теме
(7) Для приведенного примера ИМХО рекурсия не нужна. Для примера автора пожалуйста
12. venger 2121 30.06.09 15:34 Сейчас в теме
(10) Причем тут одно к другому, давайте разбираться последовательно, Вы выразили сомнения в том, что рекурсия затратнее цикла, Вам предложен чистый эксперимент, без инородных влияющих факторов. Каковы результаты?
13. Evg-Lylyk 4559 30.06.09 15:40 Сейчас в теме
(12) В приведенном примере рекурсия не нужна.
Вы пишите "Причем в 1С, уж в семерке так точно, рекурсия более затратна, чем цикл:-)" т.е. утверждаете что рекурсия более затратна, хотелось бы видеть для варианта автора
19. YVolohov 721 30.06.09 15:52 Сейчас в теме
Итак, с использованием рекурсии:

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

ВывестиЧисло(1);

0,1154 сек.

Без использования рекурсии

Для Счетчик = 1 По 100 Цикл
Сообщить(Строка(Счетчик));
КонецЦикла;

0,1118 сек.

Почти одинаково, но рекурсия все же работает немного быстреее

20. YVolohov 721 30.06.09 15:53 Сейчас в теме
(19) рекурсия работает немного медленнее
22. Evg-Lylyk 4559 30.06.09 15:55 Сейчас в теме
(19) Пример жесть!!! :)))) пожалуйста НА ПРИМЕРЕ АВТОРА ТЕМЫ
23. YVolohov 721 30.06.09 15:57 Сейчас в теме
30. venger 2121 30.06.09 16:12 Сейчас в теме
(22) +28, о вот выдали быстрее, чем я дома поставил восьмерку:-))) Пост 25-й Вас удовлетворил?:-))
31. YVolohov 721 30.06.09 16:16 Сейчас в теме
(30) меня не очень, хотелось бы увидеть это в коде
83. YVolohov 721 02.07.09 12:24 Сейчас в теме
//*******************************************
Процедура Сформировать()

Корень = СоздатьОбъект("СписокЗначений");
Ветка1 = СоздатьОбъект("СписокЗначений");
Ветка2 = СоздатьОбъект("СписокЗначений");
Для Счетчик = 1 По 10 Цикл
Корень.ДобавитьЗначение(1);
Ветка1.ДобавитьЗначение(11);
Ветка2.ДобавитьЗначение(12);
КонецЦикла;
Корень.УстановитьЗначение(4,Ветка1);
Корень.УстановитьЗначение(6,Ветка2);

//Корень - это и есть корень
ТекСписок=СоздатьОбъект("СписокЗначений");
СледСписок=СоздатьОбъект("СписокЗначений");
ТекСписок.ДобавитьЗначение(Корень);
Пока ТекСписок.РазмерСписка()<>0 Цикл
Для й=1 по ТекСписок.РазмерСписка() Цикл
Ссылка=ТекСписок.ПолучитьЗначение(й);
Если ТипЗначенияСтр(Ссылка)<>"СписокЗначений" Тогда
Сообщить(Строка(Ссылка));
Иначе //Это ветка. Вносим в список след. уровня
СледСписок.ДобавитьЗначение(Ссылка);
КонецЕсли;
КонецЦикла;
ТекСписок=СледСписок;
СледСписок=СоздатьОбъект("СписокЗначений");
КонецЦикла;
КонецПроцедуры

Вот твой алгоритм на семерке вместе с небольшим деревом, которое он должен просто обойти. При попытке его использовать компьютер просто зависает. Дерево очень простое - корень и две ветки.
Evg-Lylyk; +1 Ответить
85. Арчибальд 2706 02.07.09 13:29 Сейчас в теме
(83) Ну, конечно. По Иначе нужно в СледСписок заносить не сам список, а его элементы

Для йй=1 по Ссылка.РазмерСписка() Цикл
СледСписок.ДобавитьЗначение(Ссылка.ПолучитьЗначение(йй));
КонецЦикла;

Прошу пардону. Но минус не сниму.
87. YVolohov 721 02.07.09 13:59 Сейчас в теме
(85) Вот сейчас действительно заработало ))) Дерево обходит полностью, правда порядок обхода несколько другой чем у рекурсии или циклов.
Если корень дерева отметить как 1, подчиненные второго уровня как 11, 12, 13, 14 , третьего уровня 111, 112, 113, 114 и т. д. то цикл или рекурсия обходят так:
1 - 11 - 111 - 112 -113 -114 -12 - 112 - 113 - 114 а этот алгоритм так -
1 - 11 - 12 - 13 - 14 - 111 - 112 -113 - 114 - 121 - 122 - 123 и т.д.

Но это не играет особенной роли, если потомок не должен наследовать каких-либо свойств именно от своего предка. При установке или снятии пометки такого не требуется, поскольку все потомки наследуют свойство (состояние пометки) от общего предка (корня). Так что ты прав - альтернативный рекурсии алгоритм существует.
89. Арчибальд 2706 02.07.09 14:07 Сейчас в теме
(87)Ну да, рекурсия по каждой ветке лезет до листьев, а здесь каждый уровень последовательно обходится. Кстати, номер уровня можно фиксировать и записывать свойство, зависящее и от корневого значения, и от номера уровня.
При рекурсии труднее иметь номер уровня под рукой :))
99. Evg-Lylyk 4559 03.07.09 02:07 Сейчас в теме
(89) "При рекурсии труднее иметь номер уровня под рукой :))" легко перед вызовом процедуры рекурсии увеличить счетчик и его передать в процедуру... все..
2. Evg-Lylyk 4559 30.06.09 14:36 Сейчас в теме
Может так правильней ;)

Процедура ИзменитьПометкиПодчиненных(Строка)
Для Каждого Подчиненный Из Строка.Строки Цикл
Подчиненный.Пометка = пГлавный.Пометка;
ИзменитьПометкиПодчиненных(Подчиненный);
КонецЦикла;
КонецПроцедуры
4. YVolohov 721 30.06.09 14:39 Сейчас в теме
(2) Вобще то да, пара строчек балласта убрано :)
14. YVolohov 721 30.06.09 15:41 Сейчас в теме
Предлагаю простое сравнение, нужно написать программу которая выводит числа от 1 до 100 с помощью цикла и с помощью рекурсии и сделать замер производительности.
16. venger 2121 30.06.09 15:46 Сейчас в теме
21. Evg-Lylyk 4559 30.06.09 15:53 Сейчас в теме
(16) тем что там рекурсия не нужна. ИМХО когда рекурсия необходима ее замена не будет эффективней.
28. venger 2121 30.06.09 16:03 Сейчас в теме
(21),(22) Значит первое мы определили, при прочих равных рекурсия затратнее цикла, надеюсь Вы согласитесь:-) Причем родители в справочнике тоже дерево, по сути, чтоб Вы не питали иллюзий:-) Я про пример из форума, куда я давал ссылку, а если Вам лень замерить, то с Вами трудно говорить:-) Это раз:-)
Второе, для того, чтобы мне поиграться с обходом дерева значений, т.к. оно есть только в восьмерке, мне придется дома найти и поставить восьмерку и посмотреть, какие методы и т.п. есть у этого объекта или что оно там, ибо восьмерку в глаза не видел, так что вам придется подождать пока я найду, поставлю, поиграюсь с восьмеркой. Или восьмерошники выдадут быстрее. Так что подождите. Но по поводу затратности рекурсии по сравнению с циклом при прочих равных мы убедились или еще сомневаемся?:-)))
15. Арчибальд 2706 30.06.09 15:43 Сейчас в теме
(6, 10) В чем вопрос-то? Как обойти дерево без рекурсии? Или насколько различаются по затратам рекурсивный обход и нерекурсивный?
17. venger 2121 30.06.09 15:47 Сейчас в теме
(15) Как обойти дерево без рекурсии, а то человек волнуется и все одно и тоже повторяет, своих ошибок признать не хочет:-)))
24. Evg-Lylyk 4559 30.06.09 15:58 Сейчас в теме
(17) "Как обойти дерево без рекурсии, а то человек волнуется и все одно и тоже повторяет, своих ошибок признать не хочет:-)))" в чем моя ошибка поясните пожулайста.
25. Арчибальд 2706 30.06.09 16:01 Сейчас в теме
(17)Заводим два списка ссылок: на текущий уровень и на подчиненный. Первоначально первый список содержит сылку на корень, второй пуст.
Цикл пока не пуст первый список
Цикл по элементам первого списка
Тело: пометить подчиненные и загнать их во второй список
Конец вложенного цикла
Второй список сделать первым
Завести второй пустой список
Конец внешнего списка.
18. Dimasik2007 430 30.06.09 15:47 Сейчас в теме
А кто-нибудь замерял глубину стека в 1С?
26. YVolohov 721 30.06.09 16:02 Сейчас в теме
рекурсия 0,092427
цикл 0,056335
Но это ни о чем не говорит, да в цикле быстрее, но зато рекурсия дает дополнительные возможности. Если дерево очень большое, или размер дерева неизвестен кроме рекурсии ничего больше использовать просто нельзя.
27. Арчибальд 2706 30.06.09 16:03 Сейчас в теме
29. YVolohov 721 30.06.09 16:09 Сейчас в теме
(27) а можно это выразить в коде
32. Арчибальд 2706 30.06.09 16:19 Сейчас в теме
(29) Ну, ты сказал:)))
Описания осьмерочного языка под рукой нет.
Устроит в семерке обход дерева, где корень и ветви имеют тип СписокЗначений, а листья - другой тип?
33. YVolohov 721 30.06.09 16:22 Сейчас в теме
(32) устроит, только вот как в семерке можно реализовать дерево, там же такого объекта нет ?
38. Арчибальд 2706 30.06.09 16:42 Сейчас в теме
(33) В семерке есть все:)))

//Корень - это и есть корень
ТекСписок=СоздатьОбъект("СписокЗначений");
СледСписок=СоздатьОбъект("СписокЗначений");
ТекСписок.ДобавитьЗначение(Корень);
Пока ТекСписок.ДлинаСписка()<>0 Цикл
Для й=1 по ТекСписок.ДлинаСписка() Цикл
Ссылка=ТекСписок.ПолучитьЗначение(й);
Если ТипЗначенияСтр(Ссылка)<>"СписокЗначений" Тогда
//Это лист. Делаем с ним, что хотим, типа стамим пометку
Иначе //Это ветка. Вносим в список след. уровня
СледСписок.ДобавитьЗначение(Ссылка);
КонецЕсли;
КонецЦикла;
ТекСписок=СледСписок;
СледСписок=СоздатьОбъект("СписокЗначений");
КонецЦикла;
34. YVolohov 721 30.06.09 16:24 Сейчас в теме
35. Evg-Lylyk 4559 30.06.09 16:28 Сейчас в теме
(26) На чем тестил? А часто ли размер дерева известен? :)
(25) Не мерял, но почти уверен рекурсия будет эффективней
(28) "Значит первое мы определили, при прочих равных рекурсия затратнее цикла, надеюсь Вы согласитесь:-)" нет там совсем другой случай там рекурсия не нужна НА ПРИМЕРЕ АВТОРА ПОЖАЛУЙСТА

Для примера автора: рекурсию в 4 строки себе представляют все, а заменить рекурсию сложнее

Полный обход дерева каталогов как раз подходит для рекурсии
37. YVolohov 721 30.06.09 16:35 Сейчас в теме
(35) тестил на http://www.infostart.ru/projects/4059/
в текущей версии 2.3 используется рекурсия,
в более старой версии 2.1 используется цикл,
дерево совершенно одинаковое (4 уровня, одинаковое количество элементов), тестил на одной и той же базе, на одном и том же компьютере
46. Evg-Lylyk 4559 30.06.09 17:00 Сейчас в теме
Давайте исходит из примера автора т.к. для 90% приведенных случаев рекурсия не нужна в том числе и в варианте форума от Душелова. Я чуток знаю низкий уровень (assembler) вызов функции это очень мало операций
push АдресВозврата;
push ПеременнаяХ;
Jmp АдресПроцедуры;
+
Внутри процедуры
Одно вычитание (сдвиг стека)
и возврат

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

(37) а что делать если число уровней неизвестно
40. Арчибальд 2706 30.06.09 16:45 Сейчас в теме
36. Душелов 4013 30.06.09 16:33 Сейчас в теме
"Лучше рекурсия чисто в эстетическом плане и в понимании кода, а фактически хуже (т.к. время на запись активации функции и размещения её на стэк всяка медленнее чем обычный jump). Т.к. для данной задачи производительность не критична, лично я голосую за рекурсию."

Взято отсюда: http://forum.codenet.ru/showthread.php?t=31862
39. Душелов 4013 30.06.09 16:44 Сейчас в теме
(0) И конструкцию "Для Каждого ... Из ..." заменить на "Для ... По ...".
Это даст хороший прирост скорости.
43. YVolohov 721 30.06.09 16:56 Сейчас в теме
(39) надо будет попробовать
(40) дерево значений созданное из списков значений рулит однозначно ))), семерка действительно может все )))
Арчибальд; +1 Ответить
41. luns 30.06.09 16:50 Сейчас в теме
Все это ерунда.
Конструкции типа:
Код
Процедура ИзменитьПометкиПодчиненных(пГлавный)

    Подчиненные1 = пГлавный.Строки;
    Если Подчиненные1.Количество() = 0 Тогда
        Возврат;
    КонецЕсли;

    // Первый уровень подчиненных
    Для Каждого Подчиненный1 Из Подчиненные1 Цикл
        Подчиненный1.Пометка = пГлавный.Пометка;
        Подчиненные2 = Подчиненный1.Строки;
        Если Подчиненные2.Количество() = 0 Тогда
            Продолжить;
        КонецЕсли;

        // Второй уровень подчиненных
        Для Каждого Подчиненный2 Из Подчиненные2 Цикл
            Подчиненный2.Пометка = пГлавный.Пометка;
            Подчиненные3 = Подчиненный2.Строки;
            Если Подчиненные3.Количество() = 0 Тогда
                Продолжить;
            КонецЕсли;

            // Третий уровень подчиненных
            Для Каждого Подчиненный3 Из Подчиненные3 Цикл
                Подчиненный3.Пометка = пГлавный.Пометка;
            КонецЦикла;
        КонецЦикла;
    КонецЦикла;
КонецПроцедуры
Показать полностью


Непонятны и трудночитаемы. Выйгрыш на дереве в 4-5 вложенности будет минимальным, при вложенности 1000 страшно представить себе этот код.

Во общем наш выбор: рекурсия!
42. Арчибальд 2706 30.06.09 16:53 Сейчас в теме
(41) См. пост 36. И 39 тоже.
Кодеры, блин...
44. luns 30.06.09 16:57 Сейчас в теме
(42) И что? Можете пример для 30 уровней вложенности привести?
Выигрыш в долю микросекунды на маленьком дереве меня не интересует, если придется потратить десятки минут на то чтобы разобраться в 100 там, где достаточно 10.
48. YVolohov 721 30.06.09 17:04 Сейчас в теме
(44) в приведенном примере всего 4 уровня, причем в http://infostart.ru/projects/4059/ где изначально использовалась процедура из (41) размер дерева и структура фиксированы (корень, коллекции, объекты, таблицы). Если дерево больше, я согласен что надо использовать рекурсию. Да собственно и в этом примере она целесообразнее. Но если дерево небольшое, и размер его фиксирован, то не принципиально что использовать.
47. Арчибальд 2706 30.06.09 17:02 Сейчас в теме
(44,45) Я ж и привел в 25 и 38. Количество уровней не лимитировано. А авторский текст, процитированный в (41) - жесть, что я попытался выразить в 42 посте...

ВоооООтоЧемрееееЕчь...
56. YVolohov 721 30.06.09 17:31 Сейчас в теме
Итак к чему мы пришли:

вариант приведенный в (41) основан на циклах, выполняется быстрее рекурсии, но не подходит для слишком больших деревьев или деревьев с неизвестным количеством уровней;

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

вариант предложенный Арчибальдом, построен на циклах, поэтому не имеет недостатков рекурсии, подходит для деревьев любого размера, но код его менее читабельный чем рекурсия, к тому же требует адаптации к 8-ке.
60. Evg-Lylyk 4559 30.06.09 18:37 Сейчас в теме
(56) Осталось только все выводы учесть в шапке статьи как оказалось все не однозначно :)))
Кстати про недостаток рекурсии "переполнение стека" это происходит при большом уровне вложенности что крайне редко. ИМХО "замены" потребляют не меньше памяти
61. YVolohov 721 30.06.09 18:41 Сейчас в теме
(60) Адаптирую вариант Арчибальда под 8-ку (если получиться), сделаю замеры производительности по всех вариантах, вот тогда и допишу концовку статьи со сравнением. А пока еще не все ясно.
Evg-Lylyk; +1 Ответить
45. luns 30.06.09 16:58 Сейчас в теме
в 100 строчка кода имелось ввиду.
49. Evg-Lylyk 4559 30.06.09 17:09 Сейчас в теме
Речь о том что рекурсия эффективней в тех случаях когда она реально необходима, пример полный обход дерева каталогов диска
Преимущество рекурсии: читабельность, модифицируемость, разница в скорости ничтожна и в большинстве случаев влияют другие факторы
52. Арчибальд 2706 30.06.09 17:18 Сейчас в теме
(49) Набор "последовательность+Ветвление+цикл" является ДОСТАТОЧНЫМ для любого алгоритма. Это постулат. Поэтому случаев, когда рекурсия НЕОБХОДИМА просто не существует. Другое дело, что рекурсия зачастую элегантней выглядит...
53. Душелов 4013 30.06.09 17:25 Сейчас в теме
(52) В ряде случаев рекурсия бывает выгоднее.

http://www.intuit.ru/department/pl/csharp/10/3.html

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

В начальном состоянии 64 кольца были надеты на первую пирамиду и упорядочены по размеру. Монахи должны переложить все кольца с первой пирамиды на вторую, выполняя единственное условие - кольцо нельзя положить на кольцо меньшего размера. При перекладывании можно использовать все три пирамиды. Монахи перекладывают одно кольцо за одну секунду. Как только они закончат свою работу, наступит конец света.

Беспокоиться о близком конце света не стоит. Задача эта не под силу и современным компьютерам. Число ходов в ней равно 264, а это, как известно, большое число, и компьютер, работающий в сотню миллионов раз быстрее монахов, не справится с этой задачей в ближайшие тысячелетия.

....

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

....

Можно показать, что последовательность ходов, реализуемая рекурсивным алгоритмом, является оптимальной, так что никакой другой алгоритм не может решить задачу за меньшее число ходов.
55. Арчибальд 2706 30.06.09 17:30 Сейчас в теме
57. Арчибальд 2706 30.06.09 17:37 Сейчас в теме
(53)Там, главное, не перепутать (чтобы кольца в конце оказались на второй, а не на третьей пирамиде). Поэтому цепочку действий оптимальнее "раскручивать" с конца, т.е. рекурсивно. Без рекурсии мы вынуждены работать с начала...
50. Душелов 4013 30.06.09 17:13 Сейчас в теме
Что пишет MSDN:

Рекурсивные процедуры

Рекурсивная процедура — это процедура, которая вызывает сама себя. Как правило, это не самый эффективный способ написания кода.


**** Рассмотрение рекурсивных процедур

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

- Использование памяти.
Приложение имеет ограниченный объем пространства для локальных переменных. Каждый раз, когда процедура вызывает саму себя, она использует больше этого пространства для дополнительных копий ее локальных переменных. Если этот процесс будет продолжаться неопределенно долго, он в конечном счете вызовет ошибку StackOverflowException.

- Эффективность.
Почти всегда можно заменить цикл для рекурсии. Цикл не имеет дополнительных издержек аргументов передачи, инициализации дополнительного хранилища и возврат значений. Производительность может быть гораздо выше без рекурсивного вызова.

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

- Тестирование.
Если Вы пишете рекурсивную процедуру, необходимо проверить ее очень внимательно, чтобы убедиться в в том, что она всегда удовлетворяет некоторому граничному условию. Следует также убедиться в том, что в результате слишком большого количества рекурсивных вызовов вы не израсходуете всю доступную память.
51. Душелов 4013 30.06.09 17:18 Сейчас в теме
Вопрос:
- Почему C, Pascal при реализации ЛЮБОЙ рекурсивной процедуры требует памяти, линейно возрастающей с вызовом процедур? Насколько я понимаю, в момент вызова процедуры в стек помещаются параметры процедуры. А если их нет? Адрес возврата?

Ответ:
- Да. Так или иначе запоминается адрес возврата.
Локальные переменные ещё.

Взято тут: http://www.rsdn.ru/forum/decl/2905355.flat.aspx
54. Evg-Lylyk 4559 30.06.09 17:29 Сейчас в теме
Согласен с рекомендациями, но сам знаешь что есть случаи когда рекурсия лучший выбор, пример полный обхода дерева. А все эти факторы влияют по разному в разных случаях гдето например "эффективность использования памяти" сходит на нет.
58. trad 30.06.09 18:10 Сейчас в теме
Тема безрекурсивного вывода дерева ФС не раскрыта.

ps
Если что, то под древовидным выводом я понимаю такой вывод в котором видна родственная связь элементов
59. Арчибальд 2706 30.06.09 18:13 Сейчас в теме
(58) Рекурсивного вывода, кстати, тоже...
62. trad 30.06.09 19:00 Сейчас в теме
(59)
Перем гТекст;

Процедура ВывестиПодчиненные(Каталог, Отступ="")
Перем Атрибуты;
Состояние(Каталог);

_ФС = СоздатьОбъект("ФС");
ИмяФайла = _ФС.НайтиПервыйФайл(Каталог+"*");
Пока ПустаяСтрока(ИмяФайла) = 0 Цикл

Если Лев(ИмяФайла, 1) <> "." Тогда
гТекст.ДобавитьСтроку(Отступ+ИмяФайла);
_ФС.АтрибутыФайла(Каталог+ИмяФайла,,Атрибуты);
Если Сред(Атрибуты, 4, 1) = "1" Тогда
ВывестиПодчиненные(Каталог+ИмяФайла+"\", Отступ+" ");
КонецЕсли;
КонецЕсли;

ИмяФайла = _ФС.НайтиСледующийФайл();
КонецЦикла;
КонецПроцедуры

Процедура Сформировать()
гТекст = СоздатьОбъект("Текст");
ВывестиПодчиненные("C:\");
гТекст.Показать("C:");
КонецПроцедуры
63. trad 30.06.09 19:01 Сейчас в теме
65. Арчибальд 2706 01.07.09 07:35 Сейчас в теме
(63) Да не интересно мне. Ясно же, что решаемо, и достаточно просто.

64. Evg-Lylyk 4559 30.06.09 21:35 Сейчас в теме
На 8-ке:

Процедура КнопкаВыполнитьНажатие(Кнопка)
ОбходДереваКаталоговРекурсия("D:\DISTRIB\")
КонецПроцедуры

Процедура ОбходДереваКаталоговРекурсия(Каталог)

НайдФайлы = НайтиФайлы(Каталог,"*.*");
Для Каждого Файл Из НайдФайлы Цикл
Состояние (Файл.ПолноеИмя);
Если Файл.ЭтоКаталог() Тогда
ОбходДереваКаталоговРекурсия(Файл.ПолноеИмя);
КонецЕсли;
КонецЦикла;

КонецПроцедуры


Вместо "Состояние (Файл.ПолноеИмя);" можно вставить любой код
66. orefkov 1152 01.07.09 11:35 Сейчас в теме
В цикл преобразуется только хвостовая рекурсия.
Остальные виды рекурсий в общем виде пробразуются в "цикл + стек".
Рассматривая языки более приближенные к процессору, чем 1С (такие как С / С++), стоит отметить, что организация стека при рекурсивном вызове заключается лишь в изменении стекового регистра. А вот организация объекта-стека при безрекурсивном цикле может быть довольно-таки сложна и включать в себя работу с динамической памятью (выделение/перевыделение), копировании объектов в стек и обратно и тп. Так что имхо на С и С++ для нетривиальных рекурсий довольно неплохие шансы побить их безрекурсивные аналоги.
Evg-Lylyk; +1 Ответить
67. Evg-Lylyk 4559 01.07.09 12:10 Сейчас в теме
(0) комментарии к последнему выводу
"Перейдем к недостаткам. Использование рекурсии с большой глубиной может привести к переполнению стека и ошибке в работе программы. В случае использования рекурсии быстродействие программы уменьшается сравнительно с использованием циклов. Следовательно, если количество уровней вложенности дерева относительно небольшое, а количество строк большое, то целесообразнее использовать циклы."
Неверный вывод. Для большой глубины замены рекурии будут также переполнять память.
"Следовательно, если количество уровней вложенности дерева относительно небольшое, а количество строк большое, то целесообразнее использовать циклы". Один из недостатков рекурсии доп. вызов функции, но он производится только при шаге в глубь.

(66) да и зачем реализовывать тоже самое что уже реализовано внутри "call" (вызова процедуры)
68. YVolohov 721 01.07.09 12:20 Сейчас в теме
Обновил статью, добавил в начало несколько простых примеров для лучшего понимания, провел тестирование производительности и получил определенные выводы.

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

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

Для деревьев с большим количеством строк и большим количеством уровней оптимальнее использовать рекурсию. Выигрыш в читабельности и размере кода но снижение быстродействия.

Для деревьев с малым количеством строк и малым количеством уровней нет разницы что использовать.

Для деревьев с неизвестным заранее количеством уровней можно только использовать рекурсию.
69. Evg-Lylyk 4559 01.07.09 12:35 Сейчас в теме
(68) можно увидеть примеры на которых вы тестировали т.к. я в них сомневаюсь если это "ВывестиЧисла(пЧисло)" то тогда понятно.
Для тех случаев когда рекурсия необходима она не имеет значительной потери в скорости, а должна даже выигрывать и неважно сколько в дереве уровней и строка рекурсия будет эффективной.
Еще пример для рекурсии расчет выражений например:
"С=A+B; A=10; B=A+7"

Для обхода дерева с неограниченным количеством уровней как в твоем примере для 8.х никто не привел пример. Как мне кажется я потрачу на это больше часа и точно не будет быстрее твоего варианта.
А пример 38 омеет очень много операций он не будет быстрым

79. Арчибальд 2706 02.07.09 10:01 Сейчас в теме
(68)
> Для деревьев с неизвестным заранее количеством уровней можно только использовать рекурсию.

Автор с упорством, достойным лучшего применения, отрицает очевидное. Приведен же ясный пример в 11 строк обхода произвольного дерева.
81. YVolohov 721 02.07.09 10:59 Сейчас в теме
(79) (80) Публично покаюсь, если сможешь применить этот код к восьмерочному дереву. Лично у меня не получилось.
82. Арчибальд 2706 02.07.09 11:44 Сейчас в теме
(81)К дереву на Лиспе код тоже не применим. Код опровергает утверждение статьи, цитирую
" Подведем итоги. В результате этого небольшого исследования мы выяснили, что рекурсию целесообразно использовать для работы с деревьями, имеющими большое количество уровней вложенности или деревьями, количество уровней вложенности которых не определено. В последнем случае применение рекурсии – ЕДИНСТВЕННО возможный механизм."
По поводу восьмерки. Вы хотите заявить, что восьмерка не позволяет создать ссылку на элемент (ветку) дерева? Или, что приведенный мной алгоритм неуниверсален (годится не для всяких деревьев)? Или, что дерево в восьмерке не такое как все?

70. YVolohov 721 01.07.09 12:41 Сейчас в теме
В конце статьи есть ссылка на обработку на которой я тестировал. Дерево небольшое, около 1000 строк, 4 уровня. Можешь сам попробовать. Там просто нужно заменить процедуру ИзменитьПометкиПодчиненных() на один а затем на другой вариант и посмотреть что будет быстрее. А насчет вывода чисел - так это только пример, для лучшего понимания, практического значения он не имеет.
Evg-Lylyk; +1 Ответить
71. YVolohov 721 01.07.09 12:49 Сейчас в теме
(70) около 1000 строк было на той конфигурации, на которой я тестировал, на других может быть и больше (в зависимости от количества метаданных и таблиц)
Evg-Lylyk; +1 Ответить
72. Evg-Lylyk 4559 01.07.09 13:56 Сейчас в теме
(71) Проверил. Для замены на 4 ре цикла рекурсия медленне на 30-50%. Это проблема 1С т.к. в любом "нормальном" языке программирования операция установки пометки будет в десятки раз дольше вызова функции. Можно написать что для известного числа уровней цикл быстрее на Х %. Но нужно не забывать о читаемости т.к. на 30000 строк (я просто запустил 10 раз) на моем компе ушло 1,2 сек на рекурсию и 0.89 на циклы.
Опять же если говорить о неизвестном размере дерева (как часто бывает) вопрос открытый.
YVolohov; +1 Ответить
73. YVolohov 721 01.07.09 14:13 Сейчас в теме
(72) а есть ли зависимость между количеством уровней дерева и быстодействием, или например между количеством строк и быстродействием ? Тоже вопрос открытый.
74. YVolohov 721 01.07.09 14:16 Сейчас в теме
(72) пожалуй что наиболее доступное дерево с неизвестным заведомо размером это файловая система
75. venger 2121 01.07.09 19:28 Сейчас в теме
Н-да.... Ну ладно, похоже Вы вдовоем друг друга (YVolohov, Evg-Lylyk) уговорите в верности чего угодно:-))) Ну да ладно.... Если Вам интересно и приятно, то почему бы и нет:-)
76. YVolohov 721 01.07.09 19:48 Сейчас в теме
(75) Человек старался, тестировал, пришел к определенным выводам, причем достаточно интересным. Почему он не заслуживает плюсика?
77. venger 2121 01.07.09 20:12 Сейчас в теме
(76) Вы в этом плане молодец, я не спорю. Но выводы, т.е. ИМХО, чуть позже и плюс тоже, хорошо? А пока я на море ополоснусться (мне пять минут ходу):-)
78. Evg-Lylyk 4559 02.07.09 09:25 Сейчас в теме
(75) Если что то неверно расскажи. А мне плюсов не жалко у меня их много :)))
80. Арчибальд 2706 02.07.09 10:05 Сейчас в теме
+79 О как! Оказывается и в самой статье появился вывод о неизбежности рекурсии. Это уже прямая ложь, заслуживающая жирного минуса...

ТаааАквоооОоот...
84. YVolohov 721 02.07.09 12:27 Сейчас в теме
Протестируй сам. Да, еще функцию ДлинаСписка я заменил на РазмерСписка, а то выбрасывало ошибку, а больше я ничего не менял.
Арчибальд; +1 Ответить
86. Арчибальд 2706 02.07.09 13:33 Сейчас в теме
А вот плюсик за тестирование выдам...
88. YVolohov 721 02.07.09 14:02 Сейчас в теме
Сейчас попробую сделать то же для восьмерки.
90. YVolohov 721 02.07.09 14:38 Сейчас в теме
Процедура ИзменитьПометкиПодчиненных(пГлавный)
СтрокиДереваА = Новый Массив;
СтрокиДереваБ = Новый Массив;
СтрокиДереваА.Добавить(пГлавный);
Пока НЕ (СтрокиДереваА.Количество() = 0) Цикл
Для Каждого СтрокаДерева Из СтрокиДереваА Цикл
СтрокаДерева.Пометка = пГлавный.Пометка;
Для Каждого СтрокаДереваПодчиненная из СтрокаДерева.Строки Цикл
СтрокиДереваБ.Добавить(СтрокаДереваПодчиненная);
КонецЦикла;
КонецЦикла;
СтрокиДереваА = СтрокиДереваБ;
СтрокиДереваБ = Новый Массив;
КонецЦикла;
КонецПроцедуры

А вот и код на восьмерке, все работает, проверял. Не знаю только как это будет выглядеть с позиций быстродействия, нужно будет протестировать.
94. YVolohov 721 02.07.09 16:37 Сейчас в теме
А я и не говорю что обязательно нужно делать 19 вложенных циклов и что это единственный выход, посмотрите лучше (90). Несколько вложенных циклов это один из выходов, подходящий для деревьев с небольшим количеством уровней и большим количеством элементов.
А улыбка это хорошо, полезно для здоровья. )))
Арчибальд; +1 Ответить
95. Арчибальд 2706 02.07.09 16:57 Сейчас в теме
(94)На мой вкус, Вы еще плюс заработали. За то, что спор не перерос в скандал. Вообще-то это подразумевается, но пока, к сожалению, проблематично.
А за статью минус оставляю.
91. venger 2121 02.07.09 14:48 Сейчас в теме
Просто пару уточнений по статье:

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

Будет не бесконечный цикл, а бесконечная рекурсия. При бесконеном цикле (ниже пример) - зависания не будет, просто будет крутиться и все, но это не зависание.

Пока 1=1 Цикл
КонецЦикла;

"Рекурсию следует использовать там, где с помощью циклов решить задачу невозможно или нецелесообразно."

Нет таких задач, чтобы невозможно. А вот целесообразно, пока видел только пример про Ханойские башни.

"Если максимальное количество уровней дерева неизвестно или так велико, что использовать вложенные циклы просто неэффективно, код получиться слишком громоздкий, да еще и повторяющийся?"

Это вроде как понятно, что не сильно уж и громоздкий, а про эффектиность - рекурсия будет всегда затратней по дереву.

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

А по поводу читабельности и более легкого понимания рекурсии.
Вы пробовали простому пользователю (желательно не шибко умному и не шибко математичному) объяснить циклы, а потом рекурсию? Как думаете, что он быстрее поймет? Да и со студентами также. Циклы сразу понятны, а рекурсия не сразу всем доступна и понятна становится.... Она тяжелей воспринимается в среднем обущающимися, чем понятие цикла...
92. YVolohov 721 02.07.09 16:02 Сейчас в теме
Ну насчет бесконечного цикла или рекурсии то это не принципиально, можно сказать "бесконечное повторение одного фрагмента кода", суть от этого не меняется.

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

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

Насчет громоздкости кода - попробуйте себе представить код с девятнадцатью вложенными циклами (для обхода двадцатиуровневого дерева).

Насчет большей затратности циклов по сравнению с рекурсией - то я утверждал как раз обратное. Циклы быстрее рекурсии. И если в дереве сто тысяч элементов и скажем всего три уровня то нужно использовать циклы. Скорость выполнения увеличиться и код будет не очень большим.
А вот если в дереве три сотни элементов и двадцать уровней то попробуйте обойти все эти уровни с помощью вложенных циклов. Код будет просто кошмарным а выигрыш в скорости выполнения для дерева с тремястами элементами будет неактуальным, поскольку составит ничтожные доли секунды.

Насчет понимаемости рекурсии то тут я согласен. Циклы понять легче. А вот читабельность кода - другое дело. Сравните размеры последней и предпоследней процедуры в статье.
93. venger 2121 02.07.09 16:25 Сейчас в теме
(92) > Насчет громоздкости кода - попробуйте себе представить код с девятнадцатью вложенными циклами (для обхода двадцатиуровневого дерева).

Вы так и не поняли, что 19-ть вложенных циклов делать не нужно;-)
Остальные Ваши возражения, что принципиально, что нет, по другим уточнениям из поста 91-го тоже вызывают улыбку;-)

Н-да, похоже действительно спорить с Вами бесполезно;-) Сорри, но со статьей не согласен, пока минус...
101. Altair777 644 03.07.09 02:28 Сейчас в теме
(92) хм... при бесконечном (или непредсказуемо большом) цикле может произойти зависание пргораммы, а при бесконечной рекурсии крах системы.
108. anig99 2843 18.08.09 23:57 Сейчас в теме
(101) если мне не изменяет память, то в 1с 8 уровни вложенности рекурсии ограничены...
(0) Плюс не ставлю, так как банально, но и минус тоже, т.к. подробно и встречал 1с прогеров, которые элементарные вещи в программировании не знают.
109. Ish_2 1104 19.08.09 00:44 Сейчас в теме
(108) Статья хороша тем , что позволила выявить позиции участников последующей дискуссии : кто , как и какие аргументы предъявляет.
Что же касается предмета статьи , то подача материала мне понравилась.

Оставьте свое сообщение