Рекурсия более высокого порядка

Используя более мощные виды рекурсии, можно записывать относи­тельно лаконичными средствами и более сложные вычисления. Одновре­менно с этим, поскольку определения довольно абстрактны, растет слож­ность отладки и понимания программ.

Если в определении функции рекурсивный вызов является аргумен­том вызова этой же самой функции, то в такой рекурсии можно выделить различные порядки (order) в соответствии с тем, на каком уровне рекур­сии находится вызов. Такую форму рекурсии называют рекурсией более высокого порядка. Функции, которые мы до сих пор определяли, были функциями с рекурсией нулевого порядка. В качестве классического примера рекурсии первого порядка часто приводится функция Аккермана:

А(m, n) = n+1 при m = 0;

А(m, n) = А(m-1,1) при n = 0;

А(m, n) = А(m-1, А(m, n-1)) в остальных случаях.

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

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

Рекурсия и итерация

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

В программировании есть два средства реализации повторяющихся вычислений/процессов:

• с помощью итерации в форме цикла - последовательного повторе­ния некоторого процесса до тех пор, пока не удовлетворится некото­рое условие;

• с помощью рекурсии - вложения одной операции в другую, когда при отрицательном результате проверки условия выполнение процес­са «приостанавливается» и происходит самовключение выполняемо­го процесса сначала уже в качестве подпрограммы для еще не выпол­ненной до конца первоначальной подпрограммы.

Программы, использующие рекурсивные процедуры и функции, от­личаются простотой, наглядностью и компактностью текста. Такие каче­ства рекурсивных алгоритмов вытекают из того, что рекурсивная проце­дура/функция описывает, что нужно делать, а нерекурсивная акценти­рует внимание на том, как нужно делать. Итерация требует меньше места в памяти и машинного времени, чем рекурсия, которой необходи­мы затраты на управление стеком. Однако существуют некоторые функ­ции, которые легко можно определить рекурсивно, но которые нельзя определить в терминах обычных алгебраических выражений, например функция Аккермана. Для многих задач рекурсивная формулировка со­вершенно прозрачна, в то время как построение итерации оказывается весьма сложным делом.

Пример 7.8 Задача о ханойских башнях. Даны 3 столбика - А, В, С. На столбике А один на другом находятся 4 диска разного диаметра, и каждый меньший диск находится на большем. Требуется переместить эти 4 диска на столбик С, сохранив их взаиморасположение. Столбик В разрешается использовать как вспомогательный. За один шаг допускается перемещать только один из верхних дисков какого-либо столбика, и больший диск не разрешается класть на диск меньшего диаметра.

Для определения подхода к решению поставленной задачи рассмот­рим более общий случай с и дисками. Если мы сформулируем решение для и дисков в терминах решения для n-1дисков, то поставленная про­блема будет решена, поскольку задачу для n-1 дисков можно будет, в свою очередь, решить в терминах n-2 дисков и т. д. до тривиального случая одного диска. А для случая одного диска решение элементарно: нужно переместить единственный диск со столбика А на столбик С. Та­ким образом мы получим рекурсивное решение задачи. Рассмотрим сло­весное описание алгоритма.

1.Если n = 1, переместить единственный диск со столбика А на столбик С и остановиться.

2.Переместить верхние n-1 дисков со столбика А на столбик В, используя столбик С как вспомогательный.

3.Переместить оставшийся диск со столбика А на столбик С.

Переместить n-1 дисков со столбика В на столбик С, используя столбик А как вспомогательный.

Приведем программу Hanoi_Towers, которая решает поставленную задачу с помощью рекурсивной процедуры Move Disks. n - число дисков на столбике Source, Source - исходный столбик, Dest - столбик, на который нужно переставить диски, Тmр - вспомогательный столбик.

{Ханойские башни}

Program Hanoi_Towers;

Var

n: integer;

Procedure Move_Disks (n: byte; Source, Dest, Tmp: char); Begin {Move_Disks} if n = 1 then