Рекурсия

Рекурсия

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

Пример 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).