3. Висхідна рекурсія

Принципи роботи процедури, що написана висхідним методом рекурсії:

1. Висхідна рекурсія вимагає дві граничні умови початкову і кінцеву.

2. Рекурсивна умова процедури, що написана висхідним методом, має останнім предикатом виклик себе. Пролог визначає тип рекурсії за цією ознакою.

3. Висхідний метод рекурсії не зберігає змінні у стеку, якщо в тілі рекурсивної процедури немає предикатів, що мають альтернативні розв’язки. Таку висхідну рекурсію називають простою. Компілятор перетворює просту рекурсію в ітерацію.

4. Рекурсивна процедура, яку написано висхідним методом, і яка має в тілі предикати, що мають альтернативні розв’язки, використовує стек під конкретизовані змінні.

5. Рекурсивна процедура при кожному новому виклику себе зберігає значення своїх змінних у стеці.

6. Вільні змінні в стеку не розташовуються. Вільні змінні цілі і вільні змінні для кожного рекурсивного виклику процедури, що стоять на відповідних місцях, зчіплюються між собою.

7. Після того, як рекурсивний виклик зіставляється з граничною умовою, починається звільнення стека і при поверненні до цілі стек стає порожнім.

8. При зіставленні рекурсивного виклику з граничною умовою вільні змінні повинні конкретизуватися результатами. Тоді, через апарат зчеплення змінних, результати будуть передані в ціль, не дивлячись на то, що стек звільнено.

Робота і написання програми, що використовує висхідну рекурсію залежить від умов завдання.

Розглянемо схеми роботи висхідної рекурсії відповідно умовам завдання.

Схема написання та роботи простої висхідної рекурсії №1

Розглянемо схему написання та роботи простої висхідної рекурсії №1 на прикладі.

Завдання: Вивести на екран усі числа від 1 до 10.

Predicates

number (integer )

Goal

number (0 ).

Clauses

number (10). (1)

number (N ):-N1=N+1, write (N1), number (N1 ). (2)

В рекурсивній процедурі факт 1 гранична умова, правило два рекурсивна умова.

Специфіка даного завдання в тому, що ми не повертаємо значень змінних в ціль, а тільки виводимо на екран числа. Тому перетворення рекурсії на ітерацію не заважає виконати необхідну роботу.

Задамося питанням, щоб було, якби був відсутній факт

number(10)? Цикл відбувався б нескінченно. Тому, щоб уникнути нескінченного циклу необхідна гранична умова.

Значення аргументів рекурсивного виклику обов'язково повинні сходиться до значення аргументу факту. Інакше рекурсивний виклик ніколи не зіставився би з граничною умовою і відбулося зациклювання.

Схема написання та роботи висхідної рекурсії №2

Розглянемо програму, в який потрібно значення змінних повертати в ціль.

Завдання: Нехай треба визначити максимальну вагу багажу в пасажирів літака. Відомо, що кожен факт має наступні дані: № місця пасажиру, кількість речей і загальну вагу речей одного пасажиру.

Predicates

max (real,real)

bag (integer, integer, real)

Goal

bag (_,_,Ves), max (Ves, Res), write(Res).

Clauses

Bag(1, 2, 32.8).

Bag(2, 1, 10.4).

Bag(3, 3, 30.0).

max (Ves, Res):-bag (_,_,Ves1), Ves1>Ves, max (Ves1, Res).

max (Res, Res).

Перший предикат bag з цілі одержує значення ваги з першого факту для порівняння при знаходженні максимуму. Це значення передається в предикат max. Предикат bag з тіла правила одержує значення ваги з поточного факту і порівнює одержане значення ваги з тим, що передається в предикат при виклику процедури. Більше значення ваги стає поточним максимумом.

Змінна третього аргументу Res (результат) під час виконання рекурсії залишається увесь час вільною, тому в стеці для неї не зберігається ніяких значень. Вільні змінні Res кожного рівня рекурсії зчіплюються між собою і змінною Res з цілі. При досягненні граничної умови змінна Res конкретизується значенням другого аргументу і через апарат зчеплення підіймається до цілі. Конкретизація змінної Res виконується за рахунок того, що другим аргументом факту поставлено змінну Res і при зіставленні факту він одержує максимальне значення ваги з рекурсивного виклику.

Схема написання та роботи рекурсії №3

Схеми написання та роботи рекурсії №1 і №2 не можна застосовувати при накоплені даних.

Розглянемо приклад програми.

Завдання: Знайти загальну кількість речей у всіх пасажирів літака.

Predicates

kol (integer,integer,integer) /* номер місця, поточна кількість речей, результат*/

bag (integer,integer, real) /*номер місця, кількість речей у одного пасажиру, загальна вага багажу одного пасажиру */

Goal

kol (1,0,Res),write(Res).

Clauses

bag (1,2,10.2).

bag (3,1,17.0).

bag (4,1,5.1).

kol(N,K,Res):-bag (N,K1,_),K2=K+K1,N1=N+1, !, kol(N1,K2,Res);

N<=4, N1=N+1, !, kol(N1,K,Res);

kol(_,Res,Res).

Пролог при кожному зіставленні предикату проглядає твердження секції Clauses з початку. Тому при накопиченні даних необхідно обов'язково керувати вибором факту bag. В завданні керування відбувається номером місця пасажиру. Якщо не керувати вибором факту, при рекурсивних викликах буде розглядатися весь час перший факт.

Початкова гранична умова задається в цілі у предикаті kol. Для номера - 1, для суми - 0. Кінцева гранична умова, факт, що передає результат у вільну змінну, досягається коли N>4.

Процедура kol має дві гілки: за першою гілкою по номеру місця вибирається з факту кількість речей у пасажира і сумується; за другою гілкою пропускається номер місця, яке вільне.

Висхідні рекурсивні процедури, що написані за схемами №2, №3 не будуть перетворені компілятором в ітерацію, тому що в тілі процедури є альтернативні розв’язки для предикатів bag.

При роботі з рекурсивними процедурами часто необхідно усунути звороту в процедуру. Для цього відсік вставляють перед рекурсивним викликом. Така ситуація виникає при використанні механізму звороту.