Рекурсия

Поиск с возвратом

Одной из важнейших особенностей языка Prolog является возможность поиска всех решений. Поиск всех решений достигается использованием механизма поиска с возвратом.

Можно сформулировать четыре основных правила поиска с возвратом:

- Правило 1: подцели должны быть согласованы по порядку, слева направо;

- Правило 2: предложения проверяются в том порядке, в котором они появляются в тексте программы;

- Правило 3: когда подцель сопоставляется с заголовком правила, тело этого правила должно быть доказано (тело правила состоит, в свою очередь, из новых подцелей, которые должны быть доказаны);

- Правило 4: целевое утверждение считается согласованным, когда соответствующие факты найдены для каждой листьевой вершины дерева целей.

 

Пример:

DOMAINS

name, thing=symbol

 

PREDICATES

hobby (name, thing)

reads (name)

is_inquisitive (name)

 

CLAUSES

hobby (“Ян”, “теннис”).

hobby (“Лена”, “лыжи”).

hobby (X, “книги”):- reads (X), is_inquisitive (X).

hobby (“Лена”, “книги”).

reads (“Ян”).

is_inquisitive (“Ян”).

 

Goal: hobby (Y, “теннис”), hobby (Y, “книги”).

Y=“Ян”

 

Для управления поиском решений существует два стандартных предиката:

- предикат fail, использующийся для поддержания поиска с возвратом;

- предикат! (отсечение), использующийся для предотвращения поиска с возвратом.

 

Предикат fail всегда дает неудачу в доказательстве и, таким образом, поддерживает поиск с возвратом.

Пример.

DOMAINS

name=symbol

 

PREDICATES

father (name, name)

everybody

 

CLAUSES

father (“Павел”, “Петр”).

father (“Петр”, “Михаил”).

father (“Петр”, “Иван”).

everybody:- father (X, Y), write (X, “это отец ”, Y, “а”), nl, fail.

 

GOAL

everybody.

Результатом работы будет вывод следующих сообщений, и работа программы завершится с неуспехом:

Павел это отец Петра

Петр это отец Михаила

Петр это отец Ивана

Предикат! (отсечение) убирает все точки возврата, то есть через отсечение нельзя совершить поиск с возвратом.

Пример.

r(1):-!, a, b, c.

r(2):-!, d.

r(3):-!, e.

r(_):- write (“Это предложение-ловушка”).

 

Практическое задание №2. Рекурсия в Prolog

(выбор варианта по последней цифре номера зачетной книжки)

 

Вариант 0

Подсчитать, сколько раз встречается некоторая буква в строке. Строка и буква должны вводиться с клавиатуры. Для разделения строки на символы использовать стандартный предикат frontchar (String, Char, StringRest), позволяющий разделять строку String на первый символ Char и остаток строки StringRest.

Вариант 1

Вычислить значение n-го члена ряда Фибоначчи: f(0)=0, f(1)=1,
f(n)=f(n-1)+f(n-2).

Вариант 2

Вычислить произведение двух целых положительных чисел (используя суммирование).

Вариант 3

Подсчитать, сколько раз встречается некоторое слово в строке. Строка и слово должны вводиться с клавиатуры. Для разделения строки на слова использовать стандартный предикат fronttoken (String, Lexeme, StringRest), позволяющий разделить строку String на первое слово Lexeme и остаток строки StringRest.

Вариант 4

Поменять порядок следования букв в слове на противоположный. Для разделения строки на символы использовать стандартный предикат frontchar (String, Char, StringRest), позволяющий разделять строку String на первый символ Char и остаток строки StringRest.

Вариант 5

Вычислить сумму ряда целых нечетных чисел от 1 до n.

Вариант 6

Поменять порядок следования слов в предложении на противоположный. Для разделения строки на слова использовать стандартный предикат fronttoken (String, Lexeme, StringRest), позволяющий разделить строку String на первое слово Lexeme и остаток строки StringRest..

Вариант 7

Вычислить сумму ряда целых четных чисел от 2 до n.

Вариант 8

Организовать ввод целых положительных чисел и их суммирование до тех пор, пока сумма не превысит некоторого порогового значения. Введенные отрицательные целые числа суммироваться не должны.

Вариант 9

Организовать ввод букв и их соединение в строку до тех пор, не будет введен символ #. Для присоединения символа к строке использовать стандартный предикат frontchar (String, Char, StringRest), позволяющий присоединять символ Char к строке StringRest и получать строку String.

Методические указания:

Рекурсия

Рекурсивная процедура – это процедура, которая вызывает сама себя. Рекурсия – хороший способ для решения задач, содержащих в себе подзадачу такого же типа.

Например, задача нахождения значения факториала n! сводится к нахождению значения факториала (n-1)! и умножения найденного значения на n.

PREDICATES

factorial (integer, real)

CLAUSES

factorial (0, 1):-!. %факториал 0! равен 1 (граничное условие,
%останавливающее рекурсию)

factorial (N, FactN):- M=N-1, factorial (M, FactM), FactN= FactM*N.

%факториал n! равен (n-1)!*n (рекурсивное условие)

Goal: factorial (3, FactN)

FactN=6

 

Для наглядного представления нахождения решения удобно использовать дерево целей:

 

У рекурсии есть большой недостаток, она требует памяти. Избежать этого недостатка позволяет хвостовая рекурсия.

Рекурсия является хвостовой, если выполняются следующие условия:

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

- ранее в предложении не было возвратных точек.

 

Пример хвостовой рекурсии:

PREDICATES

count (real)

CLAUSES

count (N):- write (N), nl, NewN=N+1, count (NewN).

GOAL

count (1).

 

Примеры нехвостовой рекурсии:

PREDICATES

badcount1 (real)

badcount2 (real)

badcount3 (real)

CLAUSES

% рекурсивный вызов ‑ не последняя подцель в предложении

badcount1 (N):- write (N), NewN=N+1, count (NewN), nl.

% перед рекурсивным вызовом в предложении есть точка возврата

badcount2 (N):- N>=0, write (N), nl, NewN=N-1, badcount2 (NewN).

badcount2 (N):- write (“N – отрицательное число”).

% перед рекурсивным вызовом в предложении есть точка возврата

badcount3 (N):- write (N), nl, NewN=N+1, check(NewN), badcount3 (NewN).

check (M):- M>=0.

check (M):- M<0.

 

Для преобразования рекурсии в хвостовую для предикатов badcount2 и badcount3 достаточно воспользоваться отсечением, которое уберет все точки возврата перед рекурсивным вызовом.

 

badcount2 (N):- N>=0,!, write (N), nl, NewN=N-1, badcount2 (NewN).

badcount2 (N):- write (“N – отрицательное число”).

badcount3 (N):- write (N), nl, NewN=N+1, check(NewN),!, badcount3 (NewN).

check (M):- M>=0.

check (M):- M<0.

 

Практическое задание №3.

Знакомство с основами функционального программирования в Lisp

(выбор варианта по последней цифре номера зачетной книжки)

 

Вариант 0

Определить рекурсивную функцию, возвращающую значение n-го члена ряда Фибоначчи: f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2).

Вариант 1

Определить рекурсивную функцию для удаления последнего элемента списка.

Вариант 2

Определить рекурсивную функцию, возвращающую произведение двух целых положительных чисел (использовать суммирование).

Вариант 3

Определить рекурсивную функцию, возвращающую последний элемент списка.

Вариант 4

Определить рекурсивную функцию, возвращающую значение суммы ряда целых четных чисел от 2 до n.

Вариант 5

Определить рекурсивную функцию, возвращающую список, из которого удалены 2-ой, 4-ый и т.д. элементы.

Вариант 6

Определить рекурсивную функцию, возвращающую количество элементов в списке без какого-либо указываемого элемента.

 

 

Вариант 7

Определить рекурсивную функцию, возвращающую количество определенных элементов в списке.

Вариант 8

Определить рекурсивную функцию для циклического сдвига списка вправо на один элемент.

Вариант 9

Определить рекурсивную функцию, возвращающую список, из которого удалены 1-ой, 3-ый и т.д. элементы.

 

Методические указания: