6.2. Загальна характеристика рекурсивних методів

Рекурсивні методи мають ряд переваг перед ітераційними методами при реалізації операцій, що повторюються:

• Ними зручно оброблювати рекурсивні дані.

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

• Рекурсивна програма більш компактна.

6.3. Низхідна та висхідна рекурсії

Порівняємо низхідний і висхідний типи рекурсії:

• Рекурсивна процедура, що написана висхідним методом рекурсії, може мати всередині предикати з декількома рішеннями. Такий тип рекурсивної процедури використовує стек. При поверненні з рекурсивного предикату змінні зі стеку звільнюються. Тому для збереження рішення використовують додаткові змінні. Низхідний метод додаткових змінних не вимагає.

• При утворенні нового списку зі старого, висхідний метод змінює порядок елементів на зворотний. Низхідний метод зберігає порядок елементів в списку.

• При утворенні нового файлу зі старого, висхідний метод залишає порядок компонент файлу. Низхідний метод змінює порядок компонент файлу на зворотний.

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

7. Робота зі списками

7.1. Списки. Оголошення списків

Списком називають об’єкт, що має впорядкований набір інших об’єктів. Список може мати будь-яке скінчене число об’єктів. В Пролозі об’єкти списку можуть бути усякого типу, але всі об’єкти повинні бути одного типу. Такі списки називають однодоменними.

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

Наприклад список цілих чисел: [1, 2, 5, 7, 3, 2]. Порожній список записується [ ].

Перший елемент списку називають головою списку. Якщо відокремити від списку перший елемент, то залишок списку теж список. Такий залишок називають хвостом списку.

За першими буквами слів Head(голова) та Tail(Хвіст) в літературі прийняті позначення голови – Н, хвоста – Т. Однак, програміст може вибирати будь-які ідентифікатори для елементів списку або хвосту.

Тип списку визначається в секції Domains:

Domains

list = integer * /*список цілих чисел */

list1 = char* /*список символів */

Ідентифікатор типу список задає користувач. Він записується перед „=”. В наших прикладах: list, list1. Після „=” записується тип елементів списку. Для першого прикладу тип елементів integer для другого прикладу char. Символ „*” означає, що об’являється список.

Пролог дозволяє оголошувати тип список списків.

Наприклад:

Domains

lst1 = integer *

lst = lst1*

Щоб визначити список з елементами різних доменів, треба об’явити типом елементу складений тип. До складеного типу можуть відноситися елементи різних доменів.

Наприклад:

Domains

d = kol( integer);

ves( real);

fam(string)

lst=d*

Список визначеного типу може бути:

[fam(“Петренко”),kol(4), ves(30.2), fam(“Ким”), kol(2), ves(12.3)]