Рекурсия (Recursion) - "Не так страшен чёрт, как его малюют"

Общие принципы, проектирование, модуляризация, темплейты и шаблоны
Ответить
Аватара пользователя
IvanLis

Activity Professionalism Tutorials Gold Man of the year 2012
Автор
guru
guru
Сообщения: 5458
Зарегистрирован: 02 дек 2009, 17:44
Награды: 7
Версия LabVIEW: 2015, 2016
Откуда: СССР
Благодарил (а): 27 раз
Поблагодарили: 86 раз

Рекурсия (Recursion) - "Не так страшен чёрт, как его малюют"

Сообщение IvanLis »

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

Смысл его прост: http://kolyanlab.alfamoon.com/algoritmy ... restanovok
perestanovki_recursion.png
perestanovki_recursion.png (5.33 КБ) 11792 просмотра
Идея перебора проста. Начинаем с последнего элемента, ставим на его место все возможные варианты, и для каждого обмена запускаем тот же алгоритм, но сделаем вид, что теперь реально последнего элемента вообще не существует и последним будет считаться предпоследний и т.д. В итоге наших махинаций рано или поздно последним будет считаться первый элемент, его ни с чем переставлять уже не надо, это будет база рекурсии, и мы получили один из вариантов перестановки. Чтобы нагляднее понять, как это все работает, посмотрите на следующую схему работы для 4-х элементного набора. Все, что стоит справа от | не видно для нашего алгоритма, то есть первый, стоящий слева от | элемент - последний элемент в представлении текущей итерации рекурсии. Зеленый прямоугольник означает то, что мы нашли одну из перестановок.
Никогда не любил рекурсии, по этому всегда стараюсь их избегать. По крайней мере, еще не встретилось ни одной задачи, где без нее нельзя было бы обойтись. Никто не станет спорить, что это достаточно мощный механизм, но слабо контролируемый, так что можно легко потерять над ним контроль и локализовать ошибку.

Я по старинке, реализовал "Рекурсивный алгоритм" без рекурсии:
Generating_Permutations_(quasi_recursion).png
Generating_Permutations_(quasi_recursion).vi
lv2010
(17 КБ) 355 скачиваний
Но что, то есть магическое в слове "рекурсия" и я решил попробовать :crazy: .
Почти все примеры на просторах Internet сводятся к демонстрации возможностей рекурсии при вычислении факториала числа, но удалось найти несколько примеров: http://www.ni.com/white-paper/9387/en
И неплохую презенташку от JKI Blog:
Recursion-in-LabVIEW-JKI-Maila.pdf
(362.42 КБ) 394 скачивания
Немного покумекав переделал программу, реализовав в ней именно рекурсию в чистом виде:
Generating_Permutations.png
Generating_Permutations.vi
lv2010
(16.45 КБ) 353 скачивания
------------------------------------------------------------------------
Но я был бы не я, если бы не попробовал сравнить два варианта программ, выполняющих одну функцию :D . Сравнение выполнялось с помощью программы:
Time Test.vi
lv2010
(25.98 КБ) 337 скачиваний
И вот что получилось:
осреднение по 30 экспериментам
осреднение по 30 экспериментам
осреднение по 300 экспериментам
осреднение по 300 экспериментам
Получается, что рекурсия дает выигрыш только в самом начале, а там он особо и не нужно. А вот при больших количествах комбинаций, рекурсисия проигрывает и чем дальше, тем больше :buuh: .
Спрашивается, зачем запускать неконтролируемый процесс, который подобен водородной бомбе, если он не имеет явных преимуществ?
Может в других языках программирования с этим дело обстоит лучшим образом, но видимо не в LabVIEW. Хотя и появилась эта возможность не так давно.

p.s. Тестирование выполнялось на NoteBook, под управлением Linux. Версия LabVIEW 2010.
Сведения о ПК
Сведения о ПК
Аватара пользователя
Jakob Brontfeyn

Activity Gold Silver Black
expert
expert
Сообщения: 1729
Зарегистрирован: 28 фев 2008, 11:01
Награды: 6
Благодарил (а): 1 раз
Контактная информация:

Re: Рекурсия (Recursion) - "Не так страшен чёрт, как его мал

Сообщение Jakob Brontfeyn »

Алгоритм Евклида.
Иван, а это у меня рекурсия или нет, или как надо по другому VI оформить,
чтобы правильно выглядеть под этот слово рекурсия.
Вложения
Rekursiya_EVKLIDA.vi
(18.37 КБ) 348 скачиваний
Аватара пользователя
IvanLis

Activity Professionalism Tutorials Gold Man of the year 2012
Автор
guru
guru
Сообщения: 5458
Зарегистрирован: 02 дек 2009, 17:44
Награды: 7
Версия LabVIEW: 2015, 2016
Откуда: СССР
Благодарил (а): 27 раз
Поблагодарили: 86 раз

Re: Рекурсия (Recursion) - "Не так страшен чёрт, как его мал

Сообщение IvanLis »

Jakob Brontfeyn писал(а):Иван, а это у меня рекурсия или нет
Нет, это не рекурсия :nono: .
Рекурсия, это когда функция вызывает сама себя:
Снимок экрана от 2013-01-18 19-32-31.png
Т.е. она содержит сама себя.
По этому и говорят о "глубине" рекурсии и "выходе" из рекурсии. Рекурсия в программировании



Посмотрите видео, там наглядно показан процесс создания рекурсивной функции:

AndreyDmitriev

Activity Professionalism Tutorials Gold Black
VIP
VIP
Сообщения: 1326
Зарегистрирован: 03 фев 2010, 00:42
Награды: 6
Версия LabVIEW: 6.1 - 2024
Откуда: Германия
Благодарил (а): 1 раз
Поблагодарили: 36 раз
Контактная информация:

Re: Рекурсия (Recursion) - "Не так страшен чёрт, как его мал

Сообщение AndreyDmitriev »

Ну рекурсия хороша там, где она уместна.
Вот, к примеру, числа Фибоначчи из примера NI:
Изображение

На языке Си оно очень симпатично выглядит:

int Fib(int n)
{
if(n==0||n==1) return 1;
else return Fib(n-1)+Fib(n-2);
}

Это называется - как слышится так и пишется.

Ну и на LabVIEW тоже неплохо:

Изображение

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

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

Ну а что касается генерации перестановок, то там можно чуть оптимизировать, так как удаление из массива и вставка в массив - довольно дорогие операции.
Я б как-то вот так сделал, что ли:
Swapper.png
Скорость проверять, право лень, но полагаю что на больших n выигрыш будет на порядок, если не больше.
Аватара пользователя
IvanLis

Activity Professionalism Tutorials Gold Man of the year 2012
Автор
guru
guru
Сообщения: 5458
Зарегистрирован: 02 дек 2009, 17:44
Награды: 7
Версия LabVIEW: 2015, 2016
Откуда: СССР
Благодарил (а): 27 раз
Поблагодарили: 86 раз

Re: Рекурсия (Recursion) - "Не так страшен чёрт, как его мал

Сообщение IvanLis »

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

Это как продолжение темы: In Place Element Structure
AndreyDmitriev

Activity Professionalism Tutorials Gold Black
VIP
VIP
Сообщения: 1326
Зарегистрирован: 03 фев 2010, 00:42
Награды: 6
Версия LabVIEW: 6.1 - 2024
Откуда: Германия
Благодарил (а): 1 раз
Поблагодарили: 36 раз
Контактная информация:

Re: Рекурсия (Recursion) - "Не так страшен чёрт, как его мал

Сообщение AndreyDmitriev »

IvanLis писал(а): Я специально использовал одинаковые функции в обоих SubVI и придерживался одинаковой структуры, не смотря на то, что в функции с рекурсией отсутствует операция удаления из массива, она все равно проигрывает по временным характеристикам.
Да это понятно, рекурсия априори будет проигрывать по производительности, ведь фактически она разворачивает итерации цикла в последовательность вызовов самой себя с приличными накладными расходами (Лабвью особенно этим страдает). Ну а дальше - насколько хватит стека. При большом количестве итераций расход памяти будет чудовищный. Вообще по определению любой цикл можно развернуть в последовательность рекурсивных вызовов, равно как любую рекурсивную функцию можно заменить циклом.

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

Суммирование элементов массива:
(стоит попробовать запустить несколько десятков тысяч итераций - и LabVIEW умрёт)
recurs-sum.png
recurs-sum.png (5.63 КБ) 11676 просмотров
Ну или вот автоиндексация:
recurs-bundle.png
recurs-bundle.png (4.8 КБ) 11676 просмотров
Ещё пример - обход дерева директорий и получение всех файлов из вложенных папок:
(тут как раз тот случай, когда рекурсия слегка упрощает код)
recurs-dir.png
В примерах выше я бросил оба метода на одну диаграмму.

Ну а что касается примера с перестановками - то там вы что-то перемудрили с кластером, который хранит длину - ведь массив о своей длине и так знает.
Вот ровно то же самое, только проще:
recurs-perm.png
recurs-perm.png (5.78 КБ) 11676 просмотров
Вообще рекурсию удобно использовать при алгоритмах на графах, либо при вычислениях по рекуррентным формулам, но опять же при относительно небольшом уровне вложенности. В компиляторах опять же применяется. Её преимущество в том, что она избавляет от необходимости ручной органиции стека и как бы более "ближе" соответствует поставленной задаче, что ли, несколько уменьшая количество "обвязки", делая код более элегантным и простым для понимания. Конечно, не стоит использовать рекурсию там, где она не нужна, либо если есть опасность переполнения стека. Если бы LabVIEW была настолько интеллектуальна, чтобы сворачивать рекурсивные вызовы обратно в цикл со стеком - наступило бы счастье.
Вложения
recurs.zip
(35.72 КБ) 345 скачиваний
Riko
interested
interested
Сообщения: 8
Зарегистрирован: 27 май 2012, 20:05
Версия LabVIEW: 9.0

Re: Рекурсия (Recursion) - "Не так страшен чёрт, как его мал

Сообщение Riko »

Доброго времени суток!
Скажите, пожалуйста, а как можно узнать уровень выполнения рекурсии? Дело в том, что на каждом уровне мне нужно подсчитывать определенное значение, и параметр расчета зависит от уровня вложенности.
Аватара пользователя
IvanLis

Activity Professionalism Tutorials Gold Man of the year 2012
Автор
guru
guru
Сообщения: 5458
Зарегистрирован: 02 дек 2009, 17:44
Награды: 7
Версия LabVIEW: 2015, 2016
Откуда: СССР
Благодарил (а): 27 раз
Поблагодарили: 86 раз

Re: Рекурсия (Recursion) - "Не так страшен чёрт, как его мал

Сообщение IvanLis »

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

Вернуться в «Модели программирования»