Рекурсия

Рекурсивная процедура – это процедура, вызывающая сама себя до тех пор, пока не будет соблюдено некоторое условие, которое остановит рекурсию. Такое условие называют граничным. Рекурсивное правило всегда состоит по крайней мере из двух частей, одна из которых является нерекурсивной. Она и определяет граничное условие.

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

Пример 1.

База данных содержит следующие факты:

roditel(ivan,oleg).

roditel(inna,oleg).

roditel(oleg,dima).

roditel(oleg,marina).

Составить рекурсивное правило предок и определить всех предков и их потомков.

Решение:

DOMAINS

name=string

PREDICATES

roditel(name,name)

predok(name,name)

CLAUSES

roditel(ivan,oleg).

roditel(inna,oleg).

roditel(oleg,dima).

roditel(oleg,marina).

predok(X,Z):-roditel(X,Z). % нерекурсивная часть правила

predok(X,Z):-roditel(X,Y), % рекурсивная часть правила

predok(Y,Z).

GOAL

predok(X,Y),

write("Рredok -",X," Еgo potomok-",Y),nl,fail.

Результат выполнения программы:

Рredok -ivan Еgo potomok-oleg

Рredok -inna Еgo potomok-oleg

Рredok -oleg Еgo potomok-dima

Рredok -oleg Еgo potomok-marina

Рredok -ivan Еgo potomok-dima

Рredok -ivan Еgo potomok-marina

Рredok -inna Еgo potomok-dima

Рredok -inna Еgo potomok-marina

Пример 2. Вычисление факториала.

Решение:

PREDICATES

fact(integer,integer)

CLAUSES

fact(0,1):-!. % Факториал нуля равен единице

fact(N,F):- N1=N-1, % уменьшаем N на единицу,

fact(N1,F1), % вычисляем факториал нового числа,

F=N*F1. % а затем умножает его на N

GOAL

write("N="),readint(N),fact(N,F),write("F=",F),nl.

Результат выполнения программы:

1-й случай:

N=0

F=1

2-й случай:

N=1

F=1

3-й случай:

N=4

F=24

Пример 3

Составить программу для вычисления Y=Xⁿ, X, n – целые числа

Решение:

Составим правило stepen, состоящее из 3-х частей.

1-я часть правила (нерекурсивная) определяет, что Х⁰=1.

2-я часть правила (рекурсивная) вычисляет Хⁿ для положительного n.

3-я часть (рекурсивная) - вычисляет Хⁿ для отрицательного n (добавляется необходимое условие Х<>0)

PREDICATES

stepen(real,real,real)

CLAUSES

stepen(X,0,1):-!.

stepen(X,N,Y):-N>0,N1=N-1,stepen(X,N1,Y1),Y=Y1*X,!.

stepen(X,N,Y):-X<>0,K=-N,stepen(X,K,Z),Y=1/Z.

GOAL

write("X="),readreal(X),

write("N="),readreal(N),

stepen(X,N,Y),write("Y=",Y),nl.

Результат выполнения программы:

1-й случай:

X=3

N=2

Y=9

2-й случай:

X=2

N=-2

Y=0.25

Пример 4 . Ханойские башни

Имеется три стержня: A, B и C. На стержне А надеты N дисков разного диаметра, надетые друг на друга в порядке убывания диаметров. Необходимо переместить диски со стержня А на стержень С используя В как вспомогательный, если перекладывать можно только по одному диску и нельзя больший диск класть на меньший.

Решение:

Составим правило move, определяющее порядок переноса дисков.

1-я (нерекурсивная) часть правила определяет действие, если на стержне находится 1 диск.

2-я (рекурсивная) часть правила перемещает сначала верхние N-1 диск на стержень B, используя С как вспомогательный, затем оставшийся диск на стержень C и, наконец, диски со стержня B на C, используя А как вспомогательный.

PREDICATES

move(integer,char,char,char)

CLAUSES

move(1,A,B,C):-

write("Перенести диск с ",A," на ",C),nl,!.

move(N,A,B,C):-

M=N-1,move(M,A,C,B),

write("Перенести диск с ",A," на ",C),nl,

move(M,B,A,C).

GOAL

write("Ханойские башни"), nl,

write("Количество дисков:"), readint(N),nl,