На этом шаге мы введем понятие рекурсии более высокого порядка и проиллюстрируем ее
использование.
Выразительные возможности рекурсии уже видны из приведенных на предыдущих шагах содержательных и занимающих мало места определений.
Используя все более мощные виды рекурсии, можно записывать относительно лаконичными средствами и более сложные вычисления. Одновременно с этим растет сложность программирования и понимания программы.
Рассмотрим программирование вложенных циклов в такой форме, при которой в определении функции рекурсивный вызов является аргументом вызова этой же самой функции. В такой рекурсии можно выделить различные порядки в соответствии с тем, на каком уровне рекурсии находится вызов.
Такую форму рекурсии будем называть рекурсией более высокого порядка. Функции, которые мы до сих пор определяли, были функциями с рекурсией нулевого порядка.
Пример 1. В качестве классического примера рекурсии более высокого порядка часто приводится известная из теории рекурсивных функций функция Аккермана, пользующаяся славой "плохой" функции: она является функцией с рекурсией первого порядка, и время вычисления растет лавинообразно уже при малых значениях аргумента.
Двухместная функция Аккермана-Хермеса f от неотрицательных целых аргументов определяется соотношениями:
f(0,b) = b+1,
f(a,0) = f(a-1,1) при a>0,
f(a,b) = f(a-1,f(a,b-1)) при a>0 и b>0.
Напишем функцию, вычисляющую ее значение:
(DEFUN AKKERMAN (LAMBDA (M N)
(COND ( (EQ M 0) (+ N 1) )
( (EQ N 0) (AKKERMAN (- M 1) 1) )
( T (AKKERMAN (- M 1)
(AKKERMAN M (- N 1))) )
)
))
Подберём тестовые примеры.
******************
1) Докажем, что * f(1,b) = b+2 *
******************
f(1,b) = f(0,f(1,b-1)) = 1+f(1,b-1) = 1+f(0,f(1,b-2)) =
= 1+1+f(1,b-2) = 2+f(1,b-2) =...=
{ Применяем данный процесс b раз }
= b+f(1,0) = b+f(0,1) = b + 2 , ч.т.д.
*******************
2) Докажем, что * f(2,b) = 2b+3 *
*******************
f(2,b) = f(1,f(2,b-1)) =
{ По ранее доказанному } =
2 + f(2,b-1) =
= 2+f(1,f(2,b-2)) = 2+2+f(2,b-2) = 2+2+f(1,f(2,b-3)) =
= 2 + 2 + 2 + f(2,b-3) =
{ Применяем данный процесс b раз } =
= 2b+f(2,0) = 2b+f(1,1) = 2b + 3 , ч.т.д.
3) Докажем, что *******************
* f(3,b) = 2b+3-3 *
*******************
f(3,b) = f(2,f(3,b-1)) = 2f(3,b-1)+3 = 2[f(2,f(3,b-2))]+3 =
= 2[2f(3,b-2)+3]+3 = 2[2f(2,f(3,b-3))+3]+3 =
= 2{2[2xf(3,b-3)+3]+3}+3 =
= 2*2*2*f(3,b-3) + 2*2*3 + 2*3 + 3 =
= { После повторения данной операции b раз } =
= 2b*f(3,0) + 2b-1*3 + 2b-2*3 + 2b-1*3 +...+ 3 =
1-2b
= 2b*f(3,0) + 3*--- = 2b*f(3,0) + 3*2b -3 .
1-2
Теперь вычислим
f(3,0) = f(2,1) = f(1,f(2,0)) = 2 + f(2,0) =
2 + f(1,1) = 2+3 = 5
f(3,b) = 5*2b+3*2b-3 = 8*2b-3 , ч.т.д.
4) Пойдем дальше...
f(4,b) = f(3,f(4,b-1)) = 2f(4,b-1)+3-3
Если мы положим f(4,b)=H(b)-3, то функция H будет удовлетворять
функциональному уравнению "гиперстепени":
H(b) = 2H(b-1)
с H(0) = 3+f(4,0) = 3 + f(3,1) = 3+(24-3) = 16
Таким образом,
H(1) = 2H(0) = 216 = 3+f(4,1) --> f(4,1) = 216-3
Замечание 1. Идея функции, включающей в себя сумму, произведение, степень, гиперстепень и т.д., восходит к Вильгельму Аккерману (1896-1962). В 1926 г. Д.Гильберт поставил проблему, можно ли получить любую вычислимую функцию неким простым способом - по существу с помощью конечного применения процессов подстановки и индукции ("примитивно-рекурсивно"). Своим примером Аккерман показал в 1928 г., что это не так. Для каждого фиксированного a функция Аккермана-Хермеса, разумеется, будет примитивно-рекурсивной.
Функция Аккермана была предложена для доказательства того, что существуют непримитивно рекурсивные функции.
Замечание 2. Сопоставьте приведенную программу с программой, написанной на классическом языке императивного программирования Pascal:
PROGRAM A_k_k_e_r_m_a_n; var M,N: Integer; { -------------------------------------- } FUNCTION A_k_k (M,N: Integer): Integer; BEGIN If M=0 then A_k_k := N + 1 else If N=0 then A_k_k := A_k_k (M-1,1) else A_k_k := A_k_k (M-1,A_k_k (M,N-1)) END; { --- } BEGIN ReadLn (M,N); Writeln; Writeln (A_k_k (M,N)) END.
Пример 2. Написать функцию, реализующую вычисление значения функции Аккермана с помощью следующих формул:
X+1 , N=0
X , N=1, Y=0
A(N,X,Y) = 0 , N=2, Y=0
1 , N=3, Y=0
2 , N>=4, Y=0
A(N-1,A(N,X,Y-1),X), N<>0, Y<>0
Интересно заметить, что:
A(0,X,Y) = X+1; A(1,X,Y) = X+Y;
A(2,X,Y) = X*Y; A(3,X,Y) = XY .
(DEFUN AKKER (LAMBDA (N X Y)
(COND ( (EQ N 0) (+ X 1) )
( (AND (EQ N 1) (EQ Y 0)) X )
( (AND (EQ N 2) (EQ Y 0)) 0 )
( (AND (EQ N 3) (EQ Y 0)) 1 )
( (AND (EQ N 4) (EQ Y 0)) 2 )
( (AND (> N 4) (EQ Y 0)) 2 )
( T (AKKER (- N 1)
(AKKER N X (- Y 1))
X) )
)
))
Пример 3. Вычислите для данного N значение функции, заданной формулой: F(N) = If N>202 then N-3 else F(F(N+4))
(DEFUN RECURS1 (LAMBDA (N)
(COND (> N 202) (- N 3)
( T (RECURS1 (RECURS1 (+ N 4))) )
)
))
Пример 4. В качестве другого примера функции с рекурсией первого порядка приведем функцию ONE-LEVEL, располагающую элементы списка на одном уровне, которую мы ранее определили, используя параллельную рекурсию:
(DEFUN ONE-LEVEL (LAMBDA (L)
(INLINE L NIL)
))
; ----------------------------
(DEFUN INLINE (LAMBDA (L RESULT)
( (NULL L) RESULT )
( (ATOM L) (CONS L RESULT) )
( INLINE (CAR L) (INLINE (CDR L) RESULT) )
))
Заметим, что применяя рекурсию более высокого порядка, вычисления можно представить более абстрактно и с помощью более короткого определения, однако представить себе работу такой функции довольно сложно.
Функция INLINE работает следующим образом. Результат строится в списке RESULT. Если L - атом, то его можно непосредственно добавить в начало списка RESULT. Если L - список, и его первый элемент является атомом, то все сводится к предыдущему состоянию на следующем уровне рекурсии, но в такой ситуации, когда список RESULT содержит уже вытянутый в один уровень оставшийся хвост.
В том случае, когда и голова списка L является списком, то его сначала приводят к одному уровню. Это делается с помощью рекурсивных вызовов, погружающихся в головную ветвь до тех пор, пока там не встретится атом, который можно добавить в начало вытянутой к этому моменту в один уровень структуры. Встречающиеся таким образом атомы добавляются по одному к вытянутому хвосту. На каждом уровне при исчерпании списка на предыдущий уровень выдается набранный к данному моменту RESULT.
Пример 5. Следующее определение функции REVERSE является примером еще более глубокого уровня рекурсии:
(DEFUN REV (LAMBDA (L)
( (NULL L) L )
( (NULL (CDR L)) L )
( CONS (CAR (REV (CDR L)))
(REV (CONS (CAR L)
(REV (CDR (REV (CDR L)))))) )
))
В определении использована рекурсия второго порядка. Вычисления, представленные этим определением, понять труднее, чем прежние, более того, сложная рекурсия удлинняет вычисления.
Пример 6. Функция SUPERREVERSE возвращает список элементов из LST1, обращенных на всех уровнях.
(DEFUN SUPERREVERSE (LAMBDA (LST1 LST2)
( (NULL LST1) LST2 )
( (ATOM (CAR LST1) )
(SUPERREVERSE (CDR LST1) (CONS (CAR LST1) LST2)))
( SUPERREVERSE (CDR LST1)
(CONS (SUPERREVERSE (CAR LST1)) LST2) )
))
Пример 7. "Быстрый" вариант функции MOD для вычисления остатка при целочисленном делении.
(DEFUN MOD1 (LAMBDA (M N)
(COND ( (NOT (LESSP M (TIMES 2 N)))
(MOD1 (MOD1 M (TIMES 2 N)) N) )
( (NOT (LESSP M N))
(MOD1 (- M N) N) )
( T M )
)
))
; --------------------
(DEFUN MOD (LAMBDA (M N)
; Функция MOD для вычисления остатка
; при целочисленном делении
(COND ( (LESSP M N) M )
( T (MOD (- M N) N) )
)
))
Обычно в практическом программировании формы рекурсии более высокого порядка не используются,
но у них есть свое теоретическое и методологическое значение.
На следующем шаге мы введем понятия автоаппликации и авторепликации.
