Page 29 - 4800

3.2 Склад рекурсивної процедури

Будь-яка рекурсивна процедура повинна включати принаймні по одній з
перерахованих нижче компонент:
1. Нерекурсивна пропозиція (правило або факт), що визначає вихідний вид
процедури, тобто вид процедури в момент, припинення рекурсії. Це, так звані, граничні
умови.
2. Рекурсивне правило. Початкові підцілі, що розташовуються в тілі цього
правила, продукують нові значення аргументів. Далі розміщується рекурсивна підмета,
у якій використовуються нові значення аргументів.
Перша пропозиція процедури “предок” визначає вихідний вид процедури. Як
тільки дана пропозиція стає істинною, подальша рекурсія припиниться. Тобто, перша
пропозиція є граничною умовою.
Друга пропозиція – це рекурсивне правило. При кожному виклику дане правило
піднімається на одне покоління вгору. Підмета батько(В, Б), що входить у тіло
правила, уніфікує значення змінної В. Потім розташовується рекурсивна підмета
предок(А, В), де використовується новий аргумент.
Розглянемо ще один приклад побудови рекурсивної процедури для обчислення
факторіала будь-якого цілого числа.
З визначення факторіала відомо, що 0!=1, а факторіал будь-якого числа N може
бути обчислений як факторіал N–1, помножений на N. Це визначення є рекурсивним,
оскільки зводить задачу знаходження N! до більш простої задачі знаходження
факторіалу (N–1)! і потім множення отриманого значення на N.
Для позначення факту, що факторіал числа N рівний R, використовуємо
предикат f(N, R). Його рекурсивне визначення буде мати вигляд, що приведений у
програмі 3.1.
/* програма 3.1 */
predicates
f(integer,integer)
clauses
f(1,1) :-!.
f(N,R) :- M=N-1, f(M,V), R=V*N.
Тут перше правило визначає граничну умову для рекурсивної процедури. Друге
правило є рекурсивним, тому що друга підмета цього правила містить виклик самої
процедури, правда з зміненими першою підметою значеннями аргументів.
Реалізація виконання даної програми Пролог-системою для випадку обчислення
факторіала числа 3 (тобто 3!) приведена на рис. 3.2.
З рис. 3.2, видно, що при виконанні заданої мети f(3,X) Пролог тричі звертається
до процедури. При цьому перші два рази узгоджується друге правило, а на третьому
кроці – перше. Особливість узгодження другого правила полягає в тому, що обидва
рази виконання третьої підмети відкладається (заноситься в стек запитів) у вигляді
рекурсії другої підмети. І тільки після узгодження на третьому кроці першого правила
Пролог повертається до виконання третьої підмети. Вони послідовно, починаючи з
останньої, витягаються зі стека запитів і виконуються.

29