Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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


Поможем в написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой





Дата добавления: 2015-08-17; просмотров: 622. Нарушение авторских прав; Мы поможем в написании вашей работы!

Studopedia.info - Студопедия - 2014-2022 год . (0.017 сек.) русская версия | украинская версия
Поможем в написании
> Курсовые, контрольные, дипломные и другие работы со скидкой до 25%
3 569 лучших специалисов, готовы оказать помощь 24/7