Что такое рекурсия с возвратом

Обновлено: 30.06.2024

На днях сёрфил глобальное пространство в поисках полезных вещей и наткнулся на статью, которая мне показалась в высшей степени замечательной. Такие вещи как рекурсия и продолжения (continuations) далеко не самые простые вещи в программировании, но вместе с ней мы с вами сможем сделать ещё один шаг в их понимании.

Материал достаточно объемный, поэтому будет разбит на несколько частей. В этой части немного о рекурсии и TCO (tail-call optimization) Ссылка на источник в конце заметки.

Чем хвостовая рекурсия отличается от обычной? Какое отношение к этому имеют продолжения, что такое CPS, и как нам помогут трамплины? Это вводная статья с примерами на Python и Clojure.

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

Вот классическая реализация рекурсивного вычисления факториала на Python:

Рекурсия будет "хвостовой", если рекурсивный вызов будет последним действием функции перед возвратом результата. (т.е. находится в "хвосте" функции). Вот версия факториала с хвостовой рекурсией:

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

Все вызовы функций находятся в хвостовой позиции.

Оба этих примера очень просты, потому что содержат только один вызов в каждой функции. Всё становится более сложным, когда функция должна сделать множественные вызовы. Хороший пример - вычисление числа Фибоначчи:

У нас есть 2 рекурсивных вызова fib_rec. Преобразовать эту функцию к хвостовому варианту будет сложнее. Первая попытка:

Последнее действие функции fib_almost_tail - рекурсивный вызов. У нас получилось? Нет, т.к. есть ещё один вызов fib_almost_tail и он не в хвостовой позиции. Более продуманная попытка:

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

Взрыв стека

Рекурсивные решения стремятся быть краткими и элегантными. Однако они несут в себе опасность - возможность "взорвать" стек во время выполнения. В Python глубина стека по умолчанию - 1000. Если мы попробуем fact_rec как показано в терминале, в ответ получим:

"Кому нужно высчитывать факториал 1000?" - вопрос логичный. Однако, если используются многочисленные рекурсивные вызовы, вы столкнетесь с проблемами гораздо раньше. Например, при подсчете 50 числа Фибоначчи с помощью fib_rec вам придется очень долго ждать выполнения, хотя запрос кажется не самым серьезным. Причина - экспоненциальная сложность простой реализации.

Функция fib_tail не страдает от этих проблем, т.к. не имеет экспоненциально растущего дерева вызовов, но так же может взорвать вам стек, если будет вызвана для большого числа. Это же высказывание правдиво для fact_tail. Сама по себе хвостовая рекурсия не решает проблему переполнения стека. Нужен ещё один ингридиент, с которым мы коротко разберемся.

Решения: ТСО или преобразование к итерациям

Теперь, вместе с описанными в предыдущей секции проблемами вернемся к хвостовым вызовам. Зачем вообще стоит преобразовывать функции? Дело в том, что в некоторых языках компилятор может автоматически предотвратить наращивание стека, преобразовав хвостовой вызов в прыжок. Этот трюк называется оптимизацией хвостовой рекурсии (TCO: tail-call optimization). Язык программирования Scheme делает это с 1970. С тех же пор Scheme вдохновляет программистов писать рекурсивные алгоритмы, т.к. TCO - это ядро языка. Более молодые языки так же подхватили эту фишку - Lua, Javascript (как только ES6 станет де-факто универсальной версией).

Некоторые языки не поддерживают TCO. Например Python - Гвидо прямо заявляет, что TCO - это "unpythonic" и он не хочет этого. В конце этой статьи я объясню, почему это не такая уж и проблема для Python, как для других языков.

Для примера возьмем Clojure. Он построен на JVM и поэтому использует её семантику для вызовов (по крайней мере если нужно получить какую-то скорость). JVM не имеет полной поддержки TCO, но Clojure подходит к этой проблеме прагматично - он поощряет ручное преобразование TCO с помощью циклов.

Заметьте сходство между этим кодом и Python fib_tail показанным ранее. Это не совпадение! Как только вы преобразуете алгоритм к хвостовому вызову, вам будет очень легко пойти дальше и собрать из него цикл. Эсли бы это не было легко, компилятор не способен был бы делать такие операции уже 40 лет!

В качестве ориентира, fib_iterative на Python:

Немного более неловкая чем реализация на Clojure, но та же самая в сути. Поскольку хвостовой вызов переносит все состояния в аргументах, мы просто используем явные переменные и циклы.

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

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

Более реалистичные примеры

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

Возьмем сортировку слиянием. Реализация на Python:

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

Сортировка слиянием - это пример множественной рекурсии, которую мы уже видели в примере с числом Фибоначчи. Другая распространенная проблема - непрямая рекурсия. Её мы видели в примере четный/нечетный.

Чтобы получить более реалистичный пример рассмотрим парсер рекурсивного спуска для этой грамматики

Весь код можно увидеть здесь ( parse_term вызывает parse_fector -> parse_factor опять parse_expr. При сложном выражении стек будет содержать множество экземпляров каждой функции.

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

Автор оригинала: Eli Bendersky's.

Спасибо за чтение, особенно нетерпеливые могут перейти по ссылке и прочитать всю статью в источнике)

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

Основные преимущества использования подпрограмм:

1. Разбиение комплексной программной задачи на простые шаги (декомпозиция). Это позволяет распределить решение одной задачи между различными людьми.
2. Уменьшение повторяющегося кода.
3. Многократное использование кода в других программах, в том числе и другими программистами.
4. Сокрытие деталей реализации от пользователей подпрограммы.

Подпрограммы, которые используются часто, объединяют в библиотеки. Большинство языков программирования позволяют не только использовать готовые подпрограммы, но и писать свои. В языке C++ подпрограммы оформляются в виде функций. Вам уже приходилось использовать различные функции, например из библиотеки cmath .

Перед тем как использовать функцию, ее нужно описать. Описание функции включает объявление и определение функции.

Объявление функции (пример 7.1) включает в себя заголовок функции, заканчивающийся точкой с запятой и включающий:

имя функции f_N ;
перечень формальных параметров с их типами
( type a_1, type a_2,… , type a_N );
тип возвращаемого значения
r_type: r _type f_N (type a_1, type a_2, . type a_N);

Функции могут быть с параметрами или без параметров. Если функция не имеет параметров, то наличие круглых скобок после имени функции обязательно.

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

Главная программа на С++ также реализована в виде функции. Эта функция всегда имеет имя main . Тип результата и наличие параметров этой функции может быть различными для различных сред программирования. В среде Code::Blocks функция main() имеет тип int и не имеет параметров.

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

При вызове функции (пример 7.3) указывается ее имя и параметры, необходимые для вычислений. Эти параметры называют фактическими параметрами.

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

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

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

Пример 7.1. Объявление функций.

int kol _ cifr ( int n );
double plos_treug ( double a, double h );

Пример 7.2. Определение функции.

int kol_cifr ( int n )

while ( n > 0 )

double plos_treug ( double a, double h )

double s = a * h / 2 ;

return acos (- 1. );

В среде Dev-C++ функция main может иметь аргументы:

В среде Microsoft Visual Studio тип возвращаемого значения у функции main может быть void:

Пример 7.3. Вызов функции.

int k = kol _ cifr ( 12345 );

double s_kv = 2 * plos_treug ( a1, h1 );

В С++ объявление и определение функции может быть в разных местах. Объявление размещают до функции main , а определение после нее.

Рекурсией называется определение объекта через такой же объект.

В данном примере рекурсивной частью определения является " ',' ".

Замечание 1. Рекурсивное определение, будучи конечным, определяет бесконечное множество объектов.

Заметим также, что можно определить и по-другому:

Определение (1) называют леворекурсивным, а (2) — праворекурсивным.

Замечание 2. В рекурсивном определении обязательно (. ) должна присутствовать нерекурсивная часть.

Рекурсивное определение может быть косвенным:

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

В данном примере имеется как прямое, так и косвенное рекурсивное определение.

В программировании под рекурсией понимается:

вызов из подпрограммы самой себя (прямая рекурсия)
вызов из подпрограммы другой подпрограммы, которая вызывает исходную (косвенная рекурсия)

При косвенной рекурсии обязательно использование опережающего объявления с помощью ключевого слова forward:

Простые примеры использования рекурсии

При вызове этой процедуры произойдет рекурсивное зацикливание, т.к. рекурсивный вызов производится безусловно.

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

Исправим нашу процедуру в соответствии со сделанным выводом:

При вызове p(0) будет выведено:

Графически, рекурсивные вызовы можно изобразить так:

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

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

Пример 2. Вывести

Максимальная глубина рекурсивных вызовов называется глубиной рекурсии.
Текущая глубина называется текущим уровнем рекурсии.

Замечание. Чем больше глубина рекурсии, тем больше накладные расходы по памяти.

Графические изображения рекурсивных вызовов

Одно графическое изображение у нас уже было. Вспомним его:

Рассмотрим более детально вызов p(0) процедуры

Программный стек — это непрерывная область памяти, выделяемая программе, в частности, для размещения в ней вызываемых подпрограмм.
При каждом вызове подпрограммы на стек кладется её запись активации (ЗА), а при возврате — снимается со стека.

Т.о. на стеке фактически хранятся все значения переменной i.

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

Поэтому следующий код — очень плохой.

Замечание 2. Накладные расходы на помещение на стек ЗА, снятие ЗА со стека, а также присваивание значений формальным параметрам на стеке достаточно велики.
Поэтому если имеется простое нерекурсивное решение (итерационное), то следует использовать именно его.

Замечание 3. Любую рекурсию можно заменить итерацией.

Примеры использования рекурсии

Пример 1. Найти n! = n(n - 1)(n - 2). 2*1
Очевидно, определить n! можем следующим образом:

Тогда решение имеет вид:

Однако, заметим, что возвращаемое значение не определено для n = 0)). Но его использование при каждом рекурсивном вызове накладно. Поэтому можно "обернуть" рекурсивную подпрограмму, например, так:

Глубина рекурсии этого алгоритма равна n.

Пример 2. Найти . Дадим рекурсивное определение:

Глубина рекурсии равна:

Пример 3. Нахождение минимального элемента в массиве. Определить этот элемент можем как минимальный(один элемент, минимальный из массива без этого элемента), т.е. рекурсивное определение следующее:

В соответствии с этим имеем решение:

Глубина рекурсии равна n - 1.

Ясно, что это не очень хороший результат.
Можно значительно уменьшить глубину, если искать минимальный среди примерно равных частей массива. Т.е. нужно поделить массив пополам, найти в каждой половине минимальные элементы и сравнить их. Поиск в половине осуществляется подобным же образом, и деление производится до тех пор, пока в подмассиве не останется один элемент.
Можно еще немного оптимизировать этот алгоритм — если в подмассиве два элемента, достаточно вернуть минимальный из них.
Теперь знания количества элементов недостаточно: необходимо знать, среди каких элементов массива вести поиск. Поэтому будем в качестве параметров передавать левую (l) и правую (r) границы подмассивов.
Дадим новое рекурсивное определение:

$\log_2 n$

Глубина рекурсии такого алгоритма уже примерно равна (по количеству делений).

Пример 4. Вывод односвязного линейного списка на экран.
Вспомним, как выглядит список:

Глубина рекурсии равна длина списка - 1

Рекурсия называется концевой, если рекурсивный вызов является последним в подпрограмме.

Концевая рекурсия наиболее легко превращается в итеративный алгоритм:

Доказательство завершимости рекурсии

Добавим к рекурсивной процедуре целый параметр n:

Если при каждом рекурсивном вызове параметр n уменьшается получим вызовы

И если рекурсия завершается при n Формы рекурсивных подпрограмм

1. Действие выполняется на рекурсивном спуске

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

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

4. Каскадная рекурсия

Эта рекурсия называется каскадной, т.к. каждый вызов подпрограммы может порождать несколько рекурсивных вызовов (каскад).

5. Удаленная рекурсия:

Примером удаленной рекурсии служит функция Аккермана:

Примеры плохого и хорошего использования рекурсии

Пример плохого использования рекурсии - числа Фибоначчи

Числа Фибоначчи задаются следующим рекуррентным соотношением:

$F_1 = 1,\quad F_2 = 1,\quad F_<n+1></p> <p> = F_n + F_ \quad n\in\mathbb.$

Мы уже вычисляли их с помощью циклов. Возможно рекурсивное (плохое!) решение:

Вот что произойдет при вызове Fib(7):

дерево рекурсивных вызовов

Как видим, одни и те же числа вычисляются по несколько раз:

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

Очевидно, данный способ крайне неэффективен по сравнению с итерационным алгоритмом как по памяти, так и по времени работы. В частности, глубина рекурсии при вычислении n-того числа Фибоначчи составляет n-1.

Рекурсивный способ вычисления чисел Фибоначчи, построенный по итерационному алгоритму

Напомним итерационный алгоритм поиска n-того числа Фибоначчи:

Построим по нему рекурсивный алгоритм, передавая в каждую рекурсивную подпрограмму переменные a,b,c, меняющиеся на каждой итерации цикла. Фактически при каждом рекурсивном вызове мы будем совершать подстановку:

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

Рекурсия в данном примере - концевая. Как уже отмечалась, она легко заменяется итерацией, при этом как раз получается предыдущее итерационное решение. Хорошие оптимизирующие компиляторы делают это автоматически.

Пример хорошего использования рекурсии - ханойские башни

Задача состоит в следующем:
Даны три стержня. На первом лежат n дисков разного радиуса при условии, что ни один диск бОльшего радиуса не лежит на диске мЕньшего радиуса.
Hеобходимо перенести диски с первого стержня на третий, пользуясь вторым, при условии:

за один ход можно переносить только один диск
меньший диск должен лежать на большем

Идея алгоритма такая:

Т.о. имеем простое рекурсивное решение:

Быстрая сортировка

Алгоритм

Очевидно, алгоритм будет работать тем быстрее, чем на более равные части мы будем делить массив (в идеале — каждый раз пополам).
Поэтому мы должны стремиться выбрать элемент x так, чтобы примерно половина элементов массива была =. С другой стороны, выбор x не должен занимать много времени и, по крайней мере, не зависеть от n — размера массива).

Мы будем использовать простейший способ выбора x — в качестве него брать первый элемент.

На следующей анимации представлен пример применения алгоритма быстрой сортировки к массиву

Рассмотрим этап 1 подробнее:
- Для разделения массива на указанные части заведем 2 индекса i и j.
- В начале i будет указывать на первый элемент и двигаться вправо, а j — на последний и двигаться влево.

Шаг 1.
Будем продвигать i вперед до тех пор, пока A[i] не станет >= x.
Далее будем продвигать j назад до тех пор, пока A[j] не станет = j.
В результате получим массив A, разделенный на 2 части:

Код программы

Асимптотическая оценка сложности

Будем исходить из того, что массив всякий раз делится на 2 одинаковые части. Это самый лучший вариант.
Глубина рекурсии в этом случае = log₂n.

Т.о., при условии деления примерно пополам, асимптотическая сложность всего алгоритма = Θ(n log n).

Теоретически доказано, что в среднем, если делим не точно пополам, асимптотическая сложность сохраняет формулу Θ(n log n).
Вопрос: какова сложность в худшем случае? Худший — когда в качестве x выбираем минимальный (или максимальный) элемент. Это происходит (в нашей ситуации, т.к. мы выбираем первый элемент), если массив уже отсортирован.
В этом случае в результате разбиения на части большая часть будет уменьшаться на 1, и глубина рекурсии в процедуре Sort будет равна .
Поэтому в худшем случае асимптотическая сложность = .

Утверждение. Для произвольных данных не существует алгоритма с асимптотической сложностью лучше, чем Θ(n log n) в среднем.

Генерация всех перестановок

Основная идея алгоритма генерации всех перестановок заключается в следующем. В массиве длины n, содержащем перестановку, будем менять последний элемент с каждым, после чего будем рекурсивно будем делать то же самое для массива длины n-1 и затем возвращать переставленный элемент на старое место. Если достигнута длина массива n=1, то переставлять ничего не нужно, а следует выдавать содержимое всего массива-перестановки на экран. Такой алгоритм позволит сгенерировать все перестановки, что следует из словесного рекурсивного определения: на последнем месте побывает каждый элемент, содержащийся в рассматриваемом массиве, после чего к оставшейся части массива рекурсивно будет применен тот же алгоритм.

Нетрудно видеть, что глубина рекурсии составляет n-1, а количество вызовов процедуры Perm составляет n!.

Генерация всех подмножеств

Генерация всех подмножеств представляет собой алгоритм перебора. В алгоритмах перебора перебираются все варианты и для подходящих вариантов выполняется определенное действие. В данном случае просто выводятся все подмножества.

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

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

Задача - научиться понимать эти пять блоков команд.

Самая известная тема для рекурсии — это расчет факториала:

Очень красивый код, но не очень понятный …

Напишем код расчета факториала согласно нашей модели (Листинг 1):

Не так красиво, как (2), но мы учимся.

н – значение для вычисления факториала;

Ф – факториал (для н=4 будет 24).

Код достаточно понятный. Заметим только то, что Ф рассчитывается на прямом пути. На обратном пути (Возврат) – ничего не происходит. Полезно отследить изменение параметров в отладчике:

Здесь использованы блоки 1 и 2.

Блок1 – как правило на практике, нужен для подготовки Условия.

Блок2 – нужен для подготовки вызова рекурсивной процедуры (функции);

Теперь можно изменить процедуру Факториал убрать параметр к и приблизить её к каноническому виду (1).

На следующем шаге заменим процедуру на функцию и уберем вычисление Ф в Блоке2.

Для полного понимания предварительно рассмотрим следующий вариант:

Возвращаться будет 1.

Строки Останов = Истина добавлены для анализа переменных Ф и н в отладчике. Теперь нет параметра Ф в виде ссылки и возвращается локальное значение Ф, которое было зафиксировано при первом входе в рекурсию.

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

На рисунке выше момент, когда вернулись в функцию, в которую входили с н = 2 и Ф = 12. Значение Ф сохранилось как для локальной переменной.

Это момент, когда еще не присвоено Ф возвращаемое значение функцией Факториал.

И вот на следующем шаге Ф переприсваивается.

В итоге функция отработает правильно.

Здесь мы не пишем функцию факториал, мы смотрим для чего нужны Блоки 1-5, как ведут себя переменные.

Рассмотрим простые примеры рекурсий в 1С.

Эта универсальная функция полезна для фиксации шапки отчета при программном выводе его:

Здесь Кз - высота заголовка, Кг – высота шапки.

Функция упрощена для примера. Настройки – настройки варианта макета, объявленные в Перем:

Рекурсивная функция написана в стиле листинга 1 и предельно понятна.

Основное применение рекурсии нашли при работе с деревьями. В 1С это в основном работа с иерархическими справочниками.

В теории деревьев различают корень, ветки и листья. Корень (ствол) это один элемент.

В 1С корня в классическом понимании у справочника нет. Корень — это сам иерархический справочник. Группы самого верхнего уровня имеют значение метода Уровень () = 0.

Рассмотрим пример определения самого старшего родителя для произвольного элемента справочника.

Каждый узел дерева имеет в точности одного родителя, за исключением корня, у которого нет родителей.

Это значит, что при движении по дереву вверх циклы не понадобятся.

Рассмотри пример использования рекурсий при обходе иерархического справочника с целью расчета себестоимости объектов строительства.

Есть объекты строительства. Объекты связаны иерархической моделью.

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

Прямые затраты – стоимость оборудования, косвенные – работы, необходимые для монтажа и ввода в эксплуатацию оборудования.

Вот пример из реальной БД:

Для решения задачи разберем алгоритм на следующей модели:

Рис. 1. Схема дерева

Рис.2. Дерево в справочнике объектов

Три уровня иерархии. Шесть объектов строительства с прямыми затратами и три с косвенными (группы).

Рассчитаем косвенные для объектов вручную.

База распределения для объекта Объект1 = 3000+2000 = 5000;

Косвенные от Объекта1:

для Объекта11 косвенные = 500 * 3000 / 5000 = 300.

для Объекта12 косвенные = 500 * 2000 / 5000 = 200.

База распределения для объекта Объект2 = 3000+2000+1000 = 6000;

Косвенные от Объекта2:

для Объекта21 косвенные = 600 * 3000 / 6000 = 300.

для Объекта22 косвенные = 600 * 2000 / 6000 = 200.

для Объекта23 косвенные = 600 * 1000 / 6000 = 100.

База распределения для объекта Объект0 – 5000+6000+1000 = 12000;

Для Объекта01 косвенные = 2400 * 1000 / 12000 = 200.

Для Объекта11 косвенные = 2400 * 3000 / 12000 = 600.

Для Объекта12 косвенные = 2400 * 2000 / 12000 = 400.

Для Объекта21 косвенные = 2400 * 3000 / 12000 = 600.

Для Объекта22 косвенные = 2400 * 2000 / 12000 = 400.

Для Объекта23 косвенные = 2400 * 1000 / 12000 = 200.

В итоге косвенные:

Для Объекта01 косвенные = 200

Для Объекта11 косвенные = 600 + 300 = 900

Для Объекта12 косвенные = 400 + 200 = 600

Для Объекта21 косвенные = 600 + 300 = 900

Для Объекта22 косвенные = 400 + 200 = 600

Для Объекта23 косвенные = 200 + 100 = 300

Итого косвенных 3500

В запросе должно быть так:

Следующий момент - куда лучше выгружать данные:

Мы выбираем дерево, потому что

В отладчике можно посмотреть данные.

Код более понятный – объект, строки, цикл.

Есть возможность реквизиты дерева использовать для алгоритма (записывать в реквизиты данные).

В интернете много статей обхода дерева как такового. А вот обход дерева, сгенерированного запросом, рассмотрен крайне скупо. Для выборки - статей написано много.

Поэтому рассмотрим алгоритм обхода дерева вниз и вверх - подробно.

Объявляем переменную ОбъектыДляПриемки, которая будет видна во всех серверных функциях.

По кнопке с клиента вызываем серверную процедуру, в которой выполняем Запрос с итогами в иерархии. Выгружаем Результат Запроса в Дерево.

с типом обхода ПоГруппировкамСИерархией. Передаем в рекурсивную функцию Строки объекта строительства, который принимаем в эксплуатацию.

Здесь важно – Объект0, это не корневой узел справочника! Но в дереве

он становится корневым (отбор по объекту).

Посмотрим данные дерева в отладчике:

Окно 1: Корень объекта строительства и его строки (Объект0)

Окно 2: Строка корня, нажимаем на ней F2

Окно 3: Строка корня раскрылась и видим Строки

Окно 4: После нажатия F2 на строке Строки

В четвертом окне 4 строки.

Проанализируем этот список (отмечен цифрой 4).

Первая строка – Объект01 – объект, который мы будем принимать к учету (это последний уровень, лист). Эта строка аналог записи в Выборке с типом – ДетальнаяЗапись.

Вторая строка – итоги по объекту Объект0. Эта строка аналог записи в Выборке с типом – ИтогПоИерархии.

Третья и четвертые строки – узлы дерева, их нужно раскрывать рекурсией.

Ниже приведены рекурсивные функции для расчета распределенных косвенных затрат.

В функции Рекурсия анализируем, какой тип строки дерева. Для детальной записи количество строк = 1 (своя строка). Для узла количество записей рано количеству потомков +1.

Запросом рассчитали суммарные значения прямых затрат для каждого узла дерева.

Во второй части условия проверяется ссылка Родителя, а если он не определён в первой части? Ответ: Если первая часть = Ложь то компилятор в условии И

не проверяет сведущие составляющие условия.

Поставим точку останова в функции КосвеныеОбъектовНаСервере как показано на рисунке ниже:

Увидим результаты запроса.

Так выглядит запись для корневой строки дерева после прохождения рекурсии. Сумма прямых затрат всех объектов нижних уровней равна 12 000.

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

Чтобы увидеть в отладчике ставим точку останове, показанную на рисунке ниже.

И сразу вызываем вторую рекурсивную функцию Косвенные.

Эта функция рассчитывает косвенные расходы для этого объекта от каждого родителя.

В итоге таблица ОбъектыДляПриемки будет выглядеть следующим образом:

Результат соответствует ручному расчету (Листинг 3).

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

Добавим в таблицу ОбъектыДляПриемки колонку Прямые.

В результате расчета получим такую таблицу:

В этом варианте не используется вторая рекурсивная функция на прямом обходе дерева. Рассчитываем необходимые данные на обратном ходе. Конечно

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

Выводы являются субъективным мнением автора.

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

Рассматривать целесообразность и использовать обратный ход рекурсивного расчета (область кода после выхода из рекурсивной функции).

В программировании рекурсия, или же рекурсивная функция — это такая функция, которая вызывает саму себя.

Рекурсию также можно сравнить с матрёшкой. Первая кукла самая большая, за ней идёт точно такая же кукла, но поменьше. Суть матрёшки состоит в том, что вы можете открывать её и доставать из неё точно такую же куклу, только немного меньше. Такой продолжительный процесс длится до тех пор, пока вы не дойдёте до последней куклы, которая и прервёт цикл. Так выглядит визуальная репрезентация рекурсии.

Да, такой исход вполне возможен. Однако, как и у функции for или while , рекурсию можно прервать условием break , чтобы функция перестала вызывать саму себя.

Вот пример кода того, как можно реализовать функцию обратного отсчёта с использованием рекурсии:

Как прервать рекурсию:

Допустим, у нас имеется функция CountDown , которая принимает аргумент (n) . Чтобы реализовать обратный отсчёт, нам следует повторить последовательность действий, понижающих значение параметра. Создадим условие вида:

Если (n) больше 1 , то вызвать функцию CountDown и вернуться в начало цикла, затем вычесть единицу и снова проверить, выполняется ли условие (n) > 1 .

По умолчанию нам нужно создать базовое условие функции, возвращающее значение true , чтобы предотвратить попадание в бесконечный цикл. Базовым условием функции здесь будет условие о том, что любое значение больше 1 не вызовет прерывание цикла.

Проще говоря, рекурсия делает то же, что и код ниже:

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

Плюсы:

Рекурсивный код снижает время выполнения функции.

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

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

И всё же стоит отметить, что рекурсия не всегда выигрывает по скорости по сравнению с циклами.

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

Минусы:

Рекурсивные функции занимают много места.

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

Рекурсивные функции замедляют программу.

Несмотря на то, что уже было сказано про мемоизацию, наш код можно ускорить, если применить циклы for или while . Помимо того, что функция может быть попросту плохо написана, мы также рискуем переполнить стек, что в конечном итоге приведёт к снижению скорости и программным ошибкам.

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

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

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

Читайте также: