Дерево значений обход рекурсией

Дерево значений обход рекурсией

Термин «рекурсия» используется во многих областях знаний. В программировании рекурсия – вызов процедуры (функции) из нее же самой. Различают простую и сложную рекурсию. При простой рекурсии некоторая процедура А вызывает сама себя, пока не выполниться заданное условие выхода, или же бесконечно. В случае сложной рекурсии процедура А вызывает процедуру Б, которая опять вызывает процедуру А, и так далее до выполнения условия выхода или бесконечно. В сложной рекурсии может участвовать и больше двух процедур или функций.

Организовать рекурсию средствами встроенного языка 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://nashe1c.ru/materials-view.jsp?id=268