Page 28 - 4800

ЛАБОРАТОРНА РОБОТА № 3
РЕКУРСІЯ І РЕКУРСИВНІ ПРОЦЕДУРИ В ПРОЛОЗІ

Мета роботи: ознайомитися з рекурсією, як з алгоритмічним методом, та її
особливостями в Пролог-програмах вивчити способи побудови рекурсивних процедур
та забезпечення цілісності відносин.

3.1 Визначення поняття рекурсії

Рекурсія – алгоритмічний метод, що часто використовується у Пролозі.
Рекурсію застосовують для тих самих цілей, що і циклічні конструкції в процедурних
мовах. У рекурсивних правилах більш складні вхідні аргументи виражаються через
менш складні. Наприклад, рекурсивний набір інструкцій з завантаження контейнерів
може мати такий вид:
Для того, щоб завантажити N контейнерів, потрібно:
Якщо N=0, то зупинитися.
Якщо N>0, то завантажити один контейнер, потім завантажити ще N–1
контейнер.
Будемо вважати, що тут дано визначення процедури “завантаження N
контейнерів”, де N – аргумент процедури і позначає деяке ціле число.
Дана процедура рекурсивна, тому що останній рядок – “завантажити N–1
контейнер” – є викликом процедурою самої себе. Слід відмітити, що аргумент при
рекурсивному виклику простіший, ніж вихідний аргумент N, у тому розумінні, що (N–
1) – це число менше, ніж число N. Тому “завантаження N контейнерів” є більш
складний випадок, що виражається через менш складний випадок виконання тих же
самих дій, тобто через “завантажити N–1 контейнер”.
Класичним прикладом рекурсивного визначення в Пролозі може бути процедура
“предок”, що складається з двох правил:
предок(А, Б):-батько(А,Б).
предок(А, Б):-батько(В, Б), предок(А, В)
Сукупність цих правил визначає два способи, відповідно до яких одна особа (А)
може бути предком іншої особи (Б). Відповідно до першого правила, А є предком Б,
якщо А – батько Б, тобто А є найближчим предком Б (рис. 3.1,а).
Відповідно до другого правила А буде предком Б, якщо є дехто В, що, будучи
батьком Б, має своїм предком А. Іншими словами, А – предок Б, якщо А – предок батька
Б, тобто А – віддаленим предком Б (рис. 3.1,б). У такий спосіб друге правило залежить
від більш простої версії самого себе, тобто від підмети “предок”.

А А Іван
Батько Батько
Батько Батько

Б ... Петро Павло
Предок
Батько

Батько Олег
Батько
В
Предок
Батько Борис

Б
Предок
а) б) в)
Рисунок 3.1 – Приклади відношення “предок” і його зв'язок з відношенням “батько”: а)
А найближчий предок Б; б) А віддалений предок Б; в) приклад схеми програми.

28