Рекурсія у мові програмування Пролог

1. Означення рекурсії

1.1. У мові Пролог одним з основних методів управління виконанням програми є рекурсія. Як правило, Пролог-програма є сукупністю рекурсивних або взаємно рекурсивних визначень. Раніше ми уже зустрічалися з рекурсивним визначенням правила "повторити". Зазначимо, що рекурсивним правилом (правилом рекурсії) називають правило, яке містить само себе як компонент. Рекурсивні правила, як і правила повторень, забезпечують повторне виконання задач.

2. Схематичне подання рекурсії

2.1. <ім’я рекурсивного правила> :- <список предикатів>, <предикат умови виходу>, <список предикатів>, <ім’я рекурсивного правила>, <список предикатів>.

3. У загальному випадку тіло правила містить 5 груп предикатів:

3.1. предикати, успіх або невдача будь-якого з них на рекурсію невпливають; предикат, який визначає умову виходу, успішне виконання його викликає рекурсію, неуспіх цього предиката викликає її зупинку; список інших предикатів, їх успіх чи неуспіх на рекурсію невпливають; саме рекурсивне звернення; список предикатів, успіх чи невдача яких не впливає на рекурсію, в процесі рекурсивного виконання вони "виштовхуються" в стек і викликаються тільки після завершення рекурсії.

4. Приклад рекурсії "Обчислення факторіалу"

4.1. /* Програма: Факторіал*/ Domains chislo, factorial = integer predicates fact(chislo, factorial) clauses fact(1, 1). fact(x, Y) :  X > 1, Z = X- 1, fact(Z, X1),Y = X1*X.