close

Вход

Забыли?

вход по аккаунту

?

презентация №4.2

код для вставкиСкачать
Ю
У
р
Г
МехМат
С
П
Логическое программировыание
Презентация 4
Рекурсивные правила
У
Ю
Содержание
2
Введение в рекурсивные вычисления
Понятие рекурсии
Составные части
Общий формат записи
Примеры
У
р
Г
МехМат
С
П
У
Ю
Рекурсия в Прологе
У
р
Г
МехМат
С
3
В Прологе для реализации последовательности повторяющихся
действий используются процедура поиска с возвратом (откат) и
рекурсия
Для Пролога, в отличие от императивных языков, рекурсия является
основным приемом программирования
Откат дает возможность получить много решений в одном вопросе к
программе, а рекурсия позволяет использовать в процессе
определения предиката его самого.
Для передачи значений между правилами используется стек. Всякий
раз при рекурсивном вызове новые копии используемых значений
помещаются в стек, который в итоге может быть переполнен…
П
У
Ю
Вводный пример
У
р
МехМат
С
4
Предположим, что в базе знаний есть набор фактов, описывающий
родственные связи людей через отношение "быть родителем".
Предикат родитель имеет два аргумента. В качестве его первого
аргумента указывается имя родителя, в качестве второго - имя
ребенка. Мы хотим создать отношение "быть предком", используя
предикат родитель.
Для того чтобы один человек был предком другого человека, нужно,
чтобы он либо был его родителем, либо являлся родителем другого
его предка.
/* предком является родитель */
ancestor(X, Y):- parent(X, Y).
/* предком является родитель предка */
ancestor(X, Y):- parent(X, Z), ancestor(Z, Y).
Г
П
У
Ю
Составляющие рекурсии
У
р
Г
МехМат
С
П
5
Базис рекурсии - это предложение, определяющее некую начальную
ситуацию или ситуацию в момент прекращения. Как правило, в этом
предложении записывается некий простейший случай, при котором
ответ получается сразу даже без использования рекурсии. Так, в
приведенной выше процедуре, описывающей предикат предок,
базисом рекурсии является первое правило, в котором определено,
что ближайшими предками человека являются его родители. Это
предложение часто содержит условие, при выполнении которого
происходит выход из рекурсии или отсечение.
Шаг рекурсии - это правило, в теле которого обязательно содержится,
в качестве подцели, вызов определяемого предиката. Если мы хотим
избежать зацикливания, определяемый предикат должен вызываться
не от тех же параметров, которые указаны в заголовке правила.
Параметры должны изменяться на каждом шаге так, чтобы в итоге
либо сработал базис рекурсии, либо условие выхода из рекурсии,
размещенное в самом правиле.
У
Ю
Общий вид шага рекурсии
У
р
МехМат
С
6
Г
<имя определяемого предиката>:[<подцели>], [<условие выхода из рекурсии>],
[<подцели>], <имя определяемого предиката>,
[<подцели>].
П
У
Ю
У
р
Пример 1: вычисление
факториала для заданного числа
Г
МехМат
С
7
П
Алгоритм вычислений:
1!=1
N!=(N-1)!*N
/* факториал единицы равен единице */
/* вычислить факториал числа на единицу меньшего и умножить
его на исходное число */
Программа на Прологе:
fact(1,1).
fact(N,F):-
/* факториал единицы равен единице */
N1 is N-1,
fact(N1,F1), /* F1 = факториалу числа на единицу меньшего исходного числа
F is F1*N. /* факториал исходного числа равен произведению F1 на само
число */
Запуск:
Решения (предотвращение ошибки):
?- fact(4,X).
ERROR: Out of local stack
fact(1,1):-!. /* факториал единицы равен единице, с отсечением */
fact(N,F):- N>1, … /* убедимся, что число больше единицы в теле правила */
У
Ю
Схема вычислений
У
р
Г
МехМат
С
8
Cхема вычисления факториала с помощью нисходящей стратегии рекурсии
П
У
Ю
Правосторонняя рекурсия
9
Правосторонняя (концевая/хвостовая) рекурсия:
использует столько же оперативной памяти, сколько обычная
итерация в императивных ЯП
рекурсивный вызов определяемого предиката должен быть
последней подцелью в теле рекурсивного правила и к моменту
рекурсивного вызова не должно остаться точек возврата
(непроверенных альтернатив).
Общий формат записи хвостовой рекурсии:
<имя_предиката>:
[<подцели>],
[<условие выхода из рекурсии>],
[<подцели>],
<имя_предиката>.
У
р
Г
МехМат
С
П
У
Ю
Пример хвостовой рекурсии
У
р
Г
МехМат
С
П
10
Вычисление факториала: переделаем представленную выше
рекурсивную реализацию fact в хвостовую (правостороннюю).
Надо добавить два дополнительных параметра, которые будут использоваться нами
для хранения промежуточных результатов. Третий параметр нужен для хранения
текущего натурального числа, для которого вычисляется факториал, четвертый
параметр - для факториала числа, хранящегося в третьем параметре. На каждом шаге
будем увеличивать третий аргумент на единицу, а второй аргумент умножать на новое
значение третьего аргумента. Рекурсию нужно будет остановить, когда третий аргумент
сравняется с первым, при этом в четвертом аргументе будет накоплен искомый
факториал, который можно поместить в качестве ответа во второй аргумент.
fact2(N,F,N,F):-!. /* останавливаемся когда 3й арг. = 1му*/
fact2(N,F,N1,F1):
N2 is N1+1,
/* N2 - следующее число после числа N1 */
F2 is F1*N2, /* F2 - факториал N2 */
fact2(N,F,N2,F2).
/* рекурсивный вызов с новыми парамет.
Вызов: ?- fact4(4,X,0,1).
X = 24
Можно определить «простое через сложное»: fact(N,F):- fact2(N,F,0,1).
У
Ю
Схема вычислений
11
Cхема вычисления факториала
с помощью восходящей стратегии рекурсии
fact4(4,24,4,24).
fact4(4,X,4,24).
fact4(4,X,3,6).
fact4(4,X,2,2).
fact4(4,X,1,1).
fact4(4,X,0,1).
У
р
Г
МехМат
С
П
У
Ю
Пример 2: Числа Фибоначчи
У
р
Г
МехМат
С
12
Числа Фибоначчи можно определить так: первое и второе числа
равны единице, а каждое последующее число является суммой двух
предыдущих.
Соответственно, третье число Фибоначчи будет равно 2, четвертое
равно 3 (сумма второго числа (1) и третьего числа (2)), пятое - 5
(сумма третьего и четвертого чисел, то есть 2 и 3), шестое - 8 (сумма
четвертого и пятого, 3 и 5) и т.д.
П
У
Ю
Реализация вычислений
У
р
МехМат
С
13
Базисы рекурсии:
первое число Фибоначчи равно единице.
аналогичное утверждение про второе число Фибоначчи. Ш
Шаг рекурсии будет опираться при вычислении следующего числа
Фибоначчи не только на предшествующее ему число, но и на
предшествующее предыдущему числу. В нем будет сформулировано, что для
вычисления числа Фибоначчи с номером N сначала нужно вычислить и
сложить числа с номерами N-1 и N-2.
Итого:
fib(1,1) :- !.
/* первое число Фибоначчи равно единице */
fib(2,1) :- !.
/* второе число Фибоначчи равно единице */
fib(N,F) :
N1 is N-1,
fib(N1,F1),
N2 is N-2,
fib(N2,F2),
F
Г
/* F1 это N-1-е число Фибоначчи */
/* F2 это N-2-е число Фибоначчи */
is F1+F2. /* N-е число Фибоначчи равно сумме N-1-го и N-2-го чисел */
П
У
Ю
Левостороння рекурсия
У
р
Г
МехМат
С
П
14
Вид рекурсии, когда тело правила начинается с рекурсивного вызова
определяемого предиката, называется левосторонней рекурсией.
Она возникает в случае, когда правило порождает подцель,
эквивалентную исходной цели, которая явилась причиной использования
этого правила.
Рекурсивная подцель стоит слева от других подцелей.
С левосторонней рекурсией очень часто возникают проблемы. Поэтому
нужно стараться, если возможно, избегать ее использования в отличие от
правосторонней (хвостовой) рекурсии.
Факты, обеспечивающие завершение рекурсии, должны в программе
помещаться перед правилом, а не после него во избежание
левосторонней рекурсии.
У
15
Пример левосторонней
реекурсии
Ю
У
р
Г
МехМат
С
П
Определение предиката «человек» через отношение «родитель»:
people(X):- people(Y), parent(Y,X).
people(Tom).
При попытке согласовать целевое утверждение people(X) Пролог
вначале пытается использовать правило и рекурсивно порождает
подцель people(Y).
Попытка найти соответствие этой цели вновь приводит к выбору
первого правила и так далее.
Причина зацикливания заключается в отсутствии возможности
использования механизма возврата. Для того, чтобы начался возврат,
нужно потерпеть неудачу при проверке первого утверждения, чего не
происходит в приведенном примере.
У
Ю
Пример 3: Имитация циклов
У
р
Г
МехМат
С
П
16
Ранее мы записали аналог императивного ветвления,
воспользовавшись отсечением:
Теперь напишем, используя рекурсию и отсечение, реализацию цикла
с предусловием:
«while <условие> do <действие>»
«пока имеет место <условие>, выполнять <действие>»
ИЛИ
На Прологе цикл можно записать следующим образом:
где w – некоторый предикат…
w:- !.
w:- <условие>, <действие>, w.
Пример:
hello(0):- !.
hello(N):- N>0, write('Hello world!\n'), hello(N-1).
У
Документ
Категория
Презентации
Просмотров
28
Размер файла
842 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа