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. Заметьте также, что Математическое определение факториала рекурсивно и его реализация через рекурсивную функцию совершенно естественна. Ниже приведена программная реализация функции вычисления факториала числа на языке Паскаль. 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
|
