Подстановка определения нерекурсивного предиката на место вызова является эффективной при наличии в программе одного вызова. Подстановка определения рекурсивного предиката усложняет программу и поэтому сомнительна, хотя иногда может принести пользу; в любом случае такое преобразование считается экзотическим. Для рекурсивно определяемого предиката эффективным является другое преобразование - замена хвостовой рекурсии циклом. Тем не менее, оказывается, это преобразование является специальным случаем подстановки определения предиката на место вызова.
Существует специальный случай рекурсии, называемый хвостовой рекурсией(tail-рекурсией в языке Лисп [1]), когда можно заменить рекурсию циклом. Рекурсивный вызов предиката определяет хвостовую рекурсию, если:
· имя вызываемого предиката совпадает с именем определяемого предиката, в теле которого находится вызов;
· вызов является последней исполняемой конструкцией в определении предиката, содержащем вызов.
Через last(S) обозначим множество последних исполняемых конструкций в операторе S. Тогда: last(A; B) = last(B), last(if(C) A else B) = last(A) È last(B), last(D(e: z)) = {D(e: z)}, last(A || B) = Æ. Однако если параллельный оператор A || B реализуется последовательным исполнением A и B, например, как B; A, то last(A || B) = last(A).
Понятие хвостовой рекурсии проиллюстрируем на примерах 5.1 и 5.2 (см. разд. 5.5).
В программе умножения через сложение (см. пример 5.1)
Умн(nat a, b: nat c) { if (a = 0) c = 0 else c = b + Умн(a – 1, b) } (7.2)
рекурсивный вызов Умн(a – 1, b) не является хвостовым, поскольку после завершения исполнения вызова исполняется операция “+”. Хвостовой является рекурсия для каждого из двух рекурсивных вызовов в программе вычисления наибольшего общего делителя (см. пример 5.2):
D(nat a, b: nat c) { if (a = b) c = a else if (a < b) D(a, b – a:c) else D(a – b, b:c) }
Допустим, имеется рекурсивное определение предиката A(x: y) { S } и вызов A(e: z) с хвостовой рекурсией внутри оператора S. Тогда этот вызов должен иметь вид A(e: y), т. е. z = y, поскольку хвостовой вызов с другим набором результатов, кроме y, смысла не имеет. Подставим определение предиката A на место вызова A(e: y). В соответствии с изложенным в конце разд. 7.1 результатом подстановки определения предиката A является | x | = | e |; { S }. Обозначим через S’ оператор, полученный заменой в S подстановкой определения на место вызова A(e: y). Очевидно, можно заменить в S’ второе вхождение S передачей управления на начало оператора S’. В итоге определение предиката A преобразуется к виду: A(x: y) {M: S’’ }, где S’’ получается из S заменой вызова A(e: y) парой операторов: | x | = | e |; goto M. Данное преобразование есть трансформация замены хвостовой рекурсии циклом.
Если в рекурсивном определении предиката A все рекурсивные вызовы имеют вид хвостовой рекурсии, то применение трансформации ко всем этим вызовам преобразует тело предиката в цикл, а определении предиката A - в нерекурсивное определение. После этой трансформации становится эффективной постановка определения предиката A на место вызова A в теле другого предиката. А после проведения подстановки вызова A становится возможной серия других преобразований.
Применение трансформации замены хвостовой рекурсии циклом покажем для программы вычисления наибольшего общего делителя. Трансформация двух рекурсивных вызовов предиката D дает следующую программу:
D(nat a, nat b: nat c) {
M: if (a = b) c = a
else if (a < b) |a, b| = |a, b – a|; goto M
else |a, b| = |a – b, b|; goto M
}
Раскроем групповые операторы присваивания, а также заменим фрагмент с операторами перехода на цикл for. Получим:
D(nat a, nat b: nat c) {
for ( ; ; ) {
if (a = b) {c = a; break; }
if (a < b) b = b – a
else a = a – b
}
}
Замена фрагмента с операторами перехода на цикл for не меняет процесса исполнения. Преобразование такого рода, улучшающее структуру программы, будем называть оформлением.