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
