Рекурсия
Мощным средством программирования в ТП является рекурсия. Р – определение некоторого отношения через самого себя. Так как в ТП отсутствуют операторы цикла, то Р. служит основным средством программирования циклических процессов.
Пример 1.
предок (X, Z):- родитель (X, Y).
предок (X, Z):- родитель (X, Y), предок (Y, Z).
Пример 2. Вычисление факториала.
domains
n, f = real
predicates
factorial (n ,f)
clauses
factorial (1, 1).
factorial (N, F):- N>0, N1=N-1, factorial (N1, F1), F=F1*N.
Программа демонстрирует другой метод вычисления факториала. Здесь рекурсивный метод заменнен на итеративный. При итеративном вычислении нет обратного хода.
predicates
factorial (integer, real)
factorial_oux (integer, real, integer, real)
clauses
factorial (N, F):- factorial_oux (N, F, 1, 1).
factorial_oux (N, F, I, P):- I<=N, NewI=I+1, NewP=P*I,
factorial_oux (N, F, NewI, NewP).
factorial_oux (N, F, I, F):- I>N.
Рекурсия и эффективность
Вычисление ряда Фибоначчи.
fib (0, 0).
fib (1, 1).
fib (N, X):- N1=N-1, N2=N-2, fib (N1, X1), fib (N2, X2), X=X1+X2.
Более эффективный вариант.
fib1 (0, _, 0).
fib1 (1, 0, 1).
fib1 (N, F1, F2):- N1=N-1, fib1 (N1, F0, F1), F2=F0-F1.