Page 30 - 4800

f(3, X)
Х=6 Х=2*3
N=3, R=X
f(3, X):- M =3-1, f(M , V), X=V*3 Правило 2

M =2 V=2
f(2, V)
M =2 V=1*2
N=2, R=V
f(2, X):- M =2-1, f(M , V), V=V*2 Правило 2

M =1
f(1, V)
M =1 V=1

f(1, 1):-!. Правило 1

Рисунок 3.2 – Схема виконання рекурсивної процедури f(N,R).

3.3 Особливості виконання рекурсивних процедур Прологом-системою

При використанні рекурсії, при дуже великій кількості рекурсивних викликів,
кількість відкладених на виконання підцілей у стеку запитів постійно росте й у деякий
момент стек переповниться. На екрані з’явиться повідомлення про помилку. Частково
допомогти в цій ситуації може збільшення розміру стека, що може бути змінений за
допомогою опції меню системи Установки/Різні – Установки/Розмір стека. Однак,
якщо встановлено граничне значення, то це вже не допоможе. Недоліки, в цьому
випадку, викликані погано продуманою організацією процедур. Для прикладу,
повернемося до процедури “предок” і визначимо її трохи інакше:
предок1(А, Б):-батько(А,Б).
предок1(А, Б):-предок1(А, В), батько(В, Б).
З декларативних позицій зміст процедури “предок1” ідентичний процедурі
“предок”, але процедурні трактування істотно відрізняються. У процедурі “предок1”
змінна В не конкретизована в момент обробки підмети предок1(А, В). На практиці це
означає те, що система, виконуючи запит до процедури “предок1”, спочатку відшукає
правильні відповіді, потім буде виконувати рекурсивні дії аж до вичерпання
доступного обсягу пам'яті.
Процедура “предок1” називається процедурою з лівою рекурсією, тому що в
другому правилі рекурсивна мета стоїть ліворуч від інших підцілей. Пролог не може
надійно обробляти ліворекурсивні процедури, що обумовлено природою стратегії
рішення задач, що закладена в Пролог. Тому, будуючи рекурсивні процедури,
необхідно це враховувати. Це особливо важливо, оскільки рекурсія – це основний
алгоритмічний підхід побудови Пролог-програм.

3.4 Приклад рекурсивної процедури пошуку довжини маршруту на графі

Розглянута вище рекурсивна процедура “предок” будувалася на основі
бінарного відношення Батько(Батько, Дитина), що встановлювало логічний зв'язок
між цими двома об'єктами. Разом з тим у практиці часто бувають випадки, коли між
об'єктами існує як якісний, так і кількісний взаємозв'язок.
Прикладом такого відношення може бути відношення Дорога(Місто_1,
Місто_2, Відстань), яке характеризує не тільки наявність зв'язку між якими-небудь
містами, але і відстань між ними.

30