Рекурсивные алгоритмы — это алгоритмы, которые решают поставленные задачи с помощью приведения их к разрешению одной или более аналогичных задач, но в более коротком их представлении.
Рекурсивные алгоритмы
Под рекурсией понимается способ представления типа объектов или методов путём предварительного задания одного или больше (как правило упрощённых) его основных случаев или методик, а далее представлением на их базе правил формирования рассматриваемого типа, которые непосредственно или опосредовано ссылаются на эти основные случаи.
По-иному, рекурсия — это метод обобщённого представления объекта или воздействия через самого себя, с применением задаваемых раньше конкретных определений.
Рекурсию возможно применять, когда есть возможность выделения подобной самой себе задачи. В качестве примера можно привести задачу «Ханойские башни». Она содержит следующую постановку задачи. Монахи одного из буддийских монастырей перекладывают кольца в течение примерно уже тысячи лет. У них есть три пирамиды, на которые одеты кольца различных размерных величин. Изначально шестьдесят четыре кольца располагались надетыми на первую из пирамид в порядке убывания их размеров. Задачей монахов было перекладывание всех колец с исходной пирамиды на следующую, при соблюдении одного условия, перекладываемое кольцо не допускается класть на кольцо, размеры которого меньше. При операции перемещения колец допускается использование всех трёх пирамид. Скорость перекладывания колец монахами составляет одно кольцо в секунду. Когда они завершат свою задачу, придёт конец света. В рекурсивном варианте решение задачи будет выглядеть следующим образом. Алгоритм перемещения башни переместит необходимое число колец из пирамиды «источника» на пирамиду «приёмник» применяя «запас» в виде третьей пирамиды. При количестве колец равном одному, алгоритм будет следующим: переместите кольцо из источника в приёмник. Конец.
Если число колец больше:
- Используя рекурсию переместите все кольца, за исключением одного, из источника в запас, применяя приёмник в качестве запаса.
- Переместите последнее кольцо из источника в приёмник.
- Переместите все кольца из запаса в приёмник, применяя источник в качестве запаса.
Рекурсивные алгоритмы в программировании
Рекурсия в программировании — это обращение к процедуре (функции) напрямую из самой программы (простая рекурсия) или же с использованием других функций (сложная рекурсия).
К примеру программная функция А обращается к функции В, а функция В обращается к функции А. Число вложенных обращений к функциям или процедурам следует называть глубиной рекурсии.
Сильная сторона рекурсивного задания объекта состоит в том, что такая законченная формулировка способна описать бесконечное количество объектов. При помощи рекурсивных программ есть возможность описывать бесконечные вычислительные операции, при этом, не допуская явного повторения части программ.
Организация рекурсивных обращений в языках и операционных средах программирования, используемых на практике, почти всегда основано на механизме стека обращений. Адреса возврата и текущие переменные операции сохраняются в стеке, что позволяет каждому последующему рекурсивному обращению к этой функции использовать свой комплект текущих переменных и поэтому всё работает правильно. Но с другой стороны этот простой по организации механизм требует затрачивать на каждое обращение определённый массив оперативной памяти компьютера, что при значительной глубине рекурсии способно вызвать переполнение стека обращений. По этой причине не следует злоупотреблять использованием программ с рекурсией, которые способны привести к чрезмерно глубокой рекурсии.
Но следует заметить, что существует особый рекурсивный тип, обозначаемый как «хвостовая рекурсия». Специальные средства программных языков (компиляторы и интерпретаторы), которые поддерживают выработку оптимального кода (исходного или который исполняется), в автоматическом режиме выполняют преобразование хвостовой рекурсии в итерацию. Это позволяет обеспечить функционирование алгоритмов с хвостовыми рекурсиями в небольшом пространстве оперативной памяти. В этом случае даже практически бесконечные рекурсивные вычисления (к примеру, если рекурсией выполняется функционирование интерпретатора команд, воспринимающего пользовательские команды), не могут привести к переполнению памяти.
Но надо также отметить, что не во всех языках программирования есть правила, которые жёстко регламентируют условия работы рекурсивных операций, позволяющие в любом случае преобразовать их в итерацию. Исключением является язык Lisp, который обладает всеми необходимыми свойствами.
Рекурсивные алгоритмы в других областях
Рекурсия в физических процессах. Наглядным примером бесконечного рекурсивного алгоритма могут служить два зеркала, установленные напротив друг друга. В каждом зеркале образованы коридоры из повторяющихся отражений другого зеркала. Ещё одним вариантом бесконечного рекурсивного алгоритма выступает самовозбуждение при положительной обратной связи в усилителе электрических сигналов, то есть в случае проникновения выходного сигнала на вход усилителя. На этом принципе построены схемы генераторов, для которых режим самовозбуждения является штатным.
Рекурсивные алгоритмы присутствуют также в области лингвистики. Это, например, могут быть языковые возможности создавать вложенные конструкции и предложения. Например, исходное предложение «кошка поймала мышь» можно расширить, применяя рекурсивный алгоритм, до «Вася понял, что кошка поймала мышь». Затем «Лиза узнала, что Вася понял, что кошка поймала мышь» и так можно продолжать бесконечно. Рекурсивный алгоритм можно считать универсальным лингвистическим методом, который есть в любом естественном языке. Но существует мнение, что в некоторых языках Амазонии свойство рекурсии не заложено изначально.
