Predicates

repat

typewriter

Clauses

repeat.

repat:- repeat.

typewriter:- repeat, readchar(C), write(C),

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;

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

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

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

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

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

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

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

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