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