Рекурсия и итерация в языке Пролог

Цель работы

Изучить возможности использования рекурсивных и итерационных алгоритмов в языке Пролог.

Теоретические сведения

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

Управление поиском с возвратом Для реализации повторных вычислений в традиционных языках существует ряд операторов (for, while, repeat). Однако в языке Пролог отсутствуют их аналоги. Пролог позволяет только два вида повторений: возврат, в котором осуществляется поиск нескольких решений в одном запросе и рекурсию, в которой процедура вызывает сама себя. Для управления поиском с возвратом используются два встроенных предиката:

fail (неудача) — осуществляет вынужденное неудачное завершение выполнение предиката и, таким образом, инициирует процесс возврата.

Cut или ! (отсечение) — используется для предотвращения поиска с возвратом.

Первый repeat является утверждением, объявляющим предикат repeat истинным. Первый repeat не создает подцелей, поэтому данное правило всегда успешно.

Однако, поскольку имеется еще один вариант правила repeat, то указатель возврата устанавливается на первый repeat. Второй repeat — это правило, которое использует само себя как компоненту (третий repeat). Второй repeat вызывает третий repeat, и этот вызов вычисляется успешно, так как первый repeat всегда успешен. Поскольку для доказательства третьего repeat имеется два правила, точка возврата устанавливается на первый repeat, и т. д. Предикат repeat будет вычисляться успешно при каждой новой попытке его вызвать после возврата.

Факт (первое утверждение) будет использоваться для выполнения всех подцелей программы. Таким образом, repeat — это рекурсивное правило, которое никогда не бывает неуспешным.

В качестве примера использования предиката repeat рассмотрим следующую программу:

predicates

repat.

typewriter.

clauses

repeat.

repat: — repeat.

typewriter: — repeat, readchar©, write©,.

char_int (C, 13).

В этой программе вводимые пользователями символы (предикат readchar) отображаются на экране (предикат write) до тех пор, пока пользователь не нажмет клавишу enter. Для порождения новых решений в процессе возврата (т.е. для обеспечения ввода пользователем новых символов до нажатия клавиши enter) используется предикат repeat.

Выполнение работы

Для решения одной и той же задачи можно использовать и итерационные и рекурсивные алгоритмы. Однако программы, записанные различными способами, по своим свойствам заметно отличаются друг от друга. Поэтому нужно взвешивать, какой способ, в какой ситуации лучше. Факторами, влияющими на решение, могут быть эффективность вычислений в отношении времени или объема памяти, длина программы, ее прозрачность и понятность и т. д.

Каноническим примером рекурсивных функций является функция вычисления факториала числа. Число n! (n факториал) определяется как (n)*(n-1)*(n-2)* … *(1). Факториал числа 0 равен 1. Заметьте также, что n! = (n)*(n-1)!.

Математическое определение факториала рекурсивно и его реализация через рекурсивную функцию совершенно естественна. Ниже приведена программная реализация функции вычисления факториала числа на языке Паскаль.

procedure Factorial (N:integer; var Y: integer);

var

NewN, NewY: integer;

begin

if N = 0 then Y:= 1.

else

if N > 0 then

begin

NewN:= N — 1;

Factorial (NewN, NewY);

Y:= NewY * N.

end

end;

Как видно из приведенного листинга процедура вычисления факториала является рекурсивной, поскольку она сама вызывает себя. Ниже приведена программная реализация функции вычисления факториала числа на языке Пролог.

factorial (0, 1).

factorial (N, Y): — N>0,.

NewN = N -1,.

factorial (NewN, NewY),.

Y = NewY * N.

factorial (3, Y).

Y=6.

При выполнении целевого утверждения factorial (3, Y) получим следующую последовательность рекурсивных вызовов:

factorial (3, Y).

factorial (2, NewY).

factorial (1, NewY').

factorial (0, NewY'') — (0!)= 1, NewY''= 1.

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

Таким образом, факт (0!) = 1 не будет использоваться до тех пор, пока в ходе исполнения программы не будет порожден вызов, специально требующий вычисления значения 0!

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

procedure factorial (N:integer; var Y: integer);

var

I, P: integer;

begin

I:=0; P:=1;

while I < N do

begin

I:= I+1;

P:= P*I.

end;

Y:=P;

end;

Основное отличие рекурсии от итерации с точки зрения исполнения состоит в том, что рекурсия в общем случае требует объем памяти, линейно зависящий от числа выполняемых рекурсивных обращений, в то время как объем памяти, требуемый для выполнения итераций, ограничен константой, не зависящий от числа выполняемых итераций.

Существует класс рекурсивных программ (в точности тех, которые могут быть преобразованы непосредственно в итерационные программы), выполняемых с использованием постоянного объема памяти. Метод реализации, приводящий к подобной экономии памяти, называется оптимизацией остатка рекурсии или, точнее, оптимизацией последнего обращения.

Для выполнения оптимизации остатка рекурсии необходимо, чтобы соблюдались следующие условия:

Вызов рекурсивно-определенного предиката должен являться самой последней подцелью предложения.

Ранее в предложении не должно быть точек возврата.

Ниже приведена итерационная версия программы вычисления факториала числа на языке Пролог.

factorial (N, Y):-factorial (0, 1, N, Y).

factorial (N, Y, N, Y):-!.

factorial (I, P, N, Y):-I.

NewI=I+1, NewP=P*NewI,.

factorial (NewI, NewP, N, Y).

factorial (3, Y).

Y=6.

Эта программа порождает вычисления методом снизу вверх — значение 1! вычисляется исходя из значения 0!, затем значение 2! исходя из 1! и т. д. В Прологе отсутствуют «локальные» переменные для удержания промежуточных результатов и их изменения в процессе вычисления. Поэтому для реализации итерационных алгоритмов, требующих сохранения промежуточных результатов, процедуры Пролога дополняются аргументами, называемыми накопителями. Накопители являются логическими переменными, а не ячейками памяти. В процессе итерации передается не адрес, а значение. Так как логические переменные обладают свойством «одноразовой записи», то измененное значение — новая логическая переменная — передается каждый раз. Поэтому для указания измененных значений в обозначениях переменных используется префикс New. Обычно промежуточное значение соответствует результату вычисления при завершении итерации. Это значение сопоставляется результирующей переменной с помощью единичного предложения процедуры. В приведенном примере промежуточное значение факториала числа сохраняется в переменной P. Как только значение счетчика I будет равно значению N, результат вычисления факториала копируется из переменной P в переменную Y и возвращается пользователю. При выполнении целевого утверждения factorial (3, Y) получим следующую последовательность рекурсивных вызовов:

factorial (3, Y).

factorial (0, 1, 3, Y).

factorial (1, 1, 3, Y).

factorial (2, 2, 3, Y).

factorial (3, 6, 3, Y).

Y:=6.

Задание на лабораторную работу

Написать функцию, использующую метод Ньютона для вычисления квадратного корня. Метод Ньютона вычисления квадратного корня из числа x начинается с выбора начального приближения y. Это приближение считается достаточно точным, если | x — y² | <= err, где err — некоторая заранее определенная погрешность. В противном случае более точным приближением будет ½ *(y + x/y), которое можно вычислить и точно так же подвергнуть проверке на погрешность. Для получения абсолютной величины числа используйте функция abs: abs (-5) = 5.

Написать рекурсивную и итерационную программы возведения числа в степень. Предполагается использование только натуральных чисел. Возведение в степень представить как повторяющееся умножение.

Написать функции для вычисления N-го числа последовательности Фибоначчи. Каждое следующее число последовательности Фибоначчи вычисляется как сумма двух предыдущих. Два первых числа равны единице.

Контрольные вопросы

Треугольное число с индексом N — это сумма всех натуральных чисел до N включительно. Напишите рекурсивную и итерационную программы, задающую отношение triangle (N, T), истинное, если T — треугольное число с индексом N.

Написать рекурсивную и итерационную программы, реализующую вычисления.

Определить процедуру between (N1, N2, X), которая порождает все целые числа X, отвечающие условию N1 X N2.

Написать процедуру, результатом которой будет выражение, являющееся факториалом числа, и в котором числа (сомножители) упорядочены в порядке возрастания.

Например,.

fact (3, S).

S=1*2*3.