Выразительные возможности рекурсии уже видны из приведенных выше содержательных и занимающих мало места определений. Определения функций В-ОДИН-УРОВЕНЬ и ОБРАЩЕНИЕ в итеративном варианте не поместились бы на одни лист бумаги (попробуйте!). С помощью рекурсии легко работать с динамическими, заранее не определенными целиком, но достаточно регулярными структурами, такими как списки произвольной длины и глубины вложения.
Используя все более мощные виды рекурсии, можно записывать относительно лаконичными средствами и более сложные вычисления. Одновременно с этим, поскольку определения довольно абстрактны, растет сложность программирования и понимания программы.
Рассмотрим теперь программирование вложенных циклов в такой форме, при которой в определении функции рекурсивный вызов является аргументом вызова этой же самой функции. В такой рекурсии можно выделить различные порядки (order) в соответствии с тем, на каком уровне рекурсии находится вызов. Такую форму рекурсии будем называть рекурсией более высокого порядка. Функции, которые мы до сих пор определяли, были функциями с рекурсией нулевого порядка.
В качестве классического примера рекурсии более высокого порядка часто приводится известная из теории рекурсивных функций, функция Аккермана, пользующаяся славой "плохой" функции:
_(defun AKKEPMAH (m n)
(cond ((= m 0) (+ n 1))
((= n 0) (AKKEPMAH (- m 1) 1))
(t (AKKEPMAH (- m 1)
(AKKEPMAH m (- n 1))))))
AKKEPMAH
(аккерман 2 2)
7
(аккерман 3 2)
27
Функция Аккермана является функцией с рекурсией первого порядка. Ее вычисление довольно сложно, и время вычисления растет лавинообразно уже при малых значениях аргумента.
В качестве другого примера функции с рекурсией первого порядка приведем функцию В-ОДИН-УРО ВЕНЬ, располагающую элементы списка на одном уровне, которую мы ранее определили, используя параллельную рекурсию:
_(defun в-один-уровень (1)
(уровень 1 nil))
В-ОДИН-УРОВЕНЬ
_(defun ВЫРОВНЯТЬ (l результат)
(cond ((null l) результат)
((atom l) (cons l результат))
(t (ВЫРОВНЯТЬ (cdr l) результат)))))
В этом определении работа функции непосредственно сведена к базовым функциям и рекурсии первого порядка, где аргументом рекурсивного вызова является один рекурсивный вызов. В более раннем определении дополнительно к базовым функциям и рекурсии нулевого порядка мы использовали функцию APPEND. Применяя рекурсию более высокого порядка вычисления можно представить более абстрактно и с помощью более короткого определения, однако представить себе работу такой функции довольно сложно.
Функция ВЫРОВНЯТЬ работает следующим образом. Результат строится в списке РЕЗУЛЬТАТ. Если L - атом, то его можно непосредственно добавить в начало списка РЕЗУЛЬТАТ. Если L - список и его первый элемент является атомом, то все сводится к предыдущему состоянию на следующем уровне рекурсии, но в такой ситуации, когда список РЕЗУЛЬТА! содержит уже вытянутый в один уровень оставшийся хвост.
В том случае, когда и голова списка L является списком, то его сначала приводят к одному уровню. Это делается с помощью рекурсивных вызов, погружающихся з головную ветвь до тех пор, пока там не встретится атом, который можно добавить в начале вытянутой к этому моменту в один уровень структуры. Встречающиеся таким образом атомы добавляются по одному к вытянутому хвосту. На каждом уровне при исчерпании списка на предыдущий уровень выдается набранный к данному моменту РЕЗУЛЬТАТ.
Следующее определение функции REVERSE, использующей лишь базовые функции и рекурсию, является примером еще более глубокого уровня рекурсии:
_(defun REV (1)
(cond
((null l) 1)
((null (cdr l)) 1)
(t (cons
(car (REV (cdr l)))
(REV (cons (car l)
(REV (cdr (REV (cdr l) ))))))
В определении использована рекурсия второго порядка. Вычисления, представленные этим определением, понять труднее, чем прежние. Сложная рекурсия усложняет и вычисления. В этом случае невозможно вновь воспользоваться полученными ранее результатами, поэтому одни и те же результаты приходится вычислять снова и снова. Обращение списка из пяти элементов функцией REV требует 149 вызовов. Десятиэлементный список требует уже 74 409 вызовов и заметное время для вычисления! Как правило, многократных вычислений можно избежать, разбив определение на несколько частей и используя подходящие параметры для сохранения и передачи промежуточных результатов.
Обычно в практическом программировании формы рекурсии более высокого порядка не используются, но у них по крайней мере есть свое теоретическое и методологическое значение.
Похожие статьи:
