Рекурсия

Рассмотрим другое определение факториала. В нем используются счетчик C и накопитель для хранения произведения первых C натуральных чисел:

class predicates
    fact: (positive, unsigned64 [out]).
    fact1: (positive, positive, unsigned64, unsigned64 [out]).
clauses
    fact(N, F):- fact1(N, 0, 1, F).

    fact1(N, N, F, F):- !.
    fact1(N, C, X, F):- fact1(N, C + 1, (C + 1) * X, F).

Снова проследим вычисления для цели fact(3, R). Эта цель унифицируется с заголовком правила:

fact(N1, F1):- fact1(N1, 0, 1, F1).

При этом N1 = 3, F1 = R. Далее вызывается цель

fact1(3, 0, 1, R).

Эта цель унифицируется только с заголовком последнего правила:

fact1(N2, C2, X2, F2):- fact1(N2, C2 + 1, (C2 + 1) * X2, F2).

При этом N2 = 3, C2 = 0, X2 = 1, F2 = R. Теперь вызывается цель

fact1(3, 1, 1, R).

Она также унифицируется только с заголовком последнего правила:

fact1(N3, C3, X3, F3):- fact1(N3, C3 + 1, (C3 + 1) * X3, F3).

При этом N3 = 3, C3 = 1, X3 = 1, F3 = R. Вызывается цель:

fact1(3, 2, 2, R).

Она унифицируется с тем же правилом:

fact1(N4, C4, X4, F4):- fact1(N4, C4 + 1, (C4 + 1) * X4, F4).

Теперь N4 = 3, C4 = 2, X4 = 2, F4 = R. Новая цель имеет вид:

fact1(3, 3, 6, R).

Эта цель унифицируется с заголовком правила:

fact1(N5, N5, F5, F5):- !.

При этом N5 = 3, F5 = 6, R = 6. Отсечение предотвращает поиск других решений. Итак, имеем: R = 6.

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

В языке Visual Prolog имеется оптимизация хвостовой рекурсии. Копии вызываемых предикатов не создаются, а вычисления ведутся в области памяти предиката-родителя. Это позволяет многократно увеличить эффективность вычислений.

Рассмотрим недетерминированный рекурсивный предикат. В следующей программе рекурсивно определяется отношение "предок" как транзитивное замыкание отношения "родитель" (рис. 5.1).

class facts - relatives
    parent: (string Родитель, string Ребенок).
clauses
    parent("Иван", "Мария").
    parent("Анна", "Мария").
    parent("Мария", "Павел").
    parent("Мария", "Петр").
    parent("Петр", "Степан").

class predicates
    ancestor: (string Предок, string Потомок) nondeterm (o,o) (i,o).
clauses
    ancestor(X, Y):-
        parent(X, Y).
    ancestor(X, Y):-
        parent(X, Z),
        ancestor(Z, Y).

    run():-
        ancestor(X, Y),
            write(X, " - ", Y), nl,
        fail;
        _ = readLine().

Упражнение 1.

ancestor("Мария", D).

5.2. Функции

В языке Visual Prolog наряду с предикатным стилем можно использовать функции и функциональный стиль программирования. Функции объявляются следующим образом:

class predicates
    имя_функции: (домен1, домен2, …) -> домен_значений.

Например:

class predicates
    f: (real, real) -> real.
clauses
    f(X, Y) = X + Y.

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

Аналогичное определение функции f из приведенного выше примера в предикатном стиле имеет вид:

class predicates
    f: (real, real, real [out]).
clauses
    f(X, Y, X + Y).

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

domains
    fun = (real, real) -> real.

class predicates
    f : fun.
    g : fun.
clauses
    f(X, Y) = X + Y.
    g(X, Y) = X * Y.

    run():-
        (F = f; F = g),
            R = F(2, 3),
            write(R), nl,
        fail;
        _ = readLine().

В следующих двух программах генерируются натуральные числа в порядке убывания, от заданного числа n до единицы включительно. Например, цель

number(3, X)

имеет следующий набор решений:

X = 3
X = 2
X = 1

Используется сначала предикатный стиль, а затем, для сравнения, функциональный.

class predicates
    number: (positive Граница, positive Число) multi (i,o).
clauses
    number(X, X).
    number(N, X):-
        N > 1,
        number(N - 1, X).

    run():-
        number(3, X),
            write(X), nl,
        fail;
        _ = readLine().

class predicates
    number: (positive) -> positive multi.
clauses
    number(N) = N.
    number(N) = number(N - 1):-
        N > 1.

    run():-
        write(number(3)), nl,
        fail;
        _ = readLine().

Упражнение 2. Напишите генератор натуральных чисел по возрастанию от 1 до заданного числа N.

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

class predicates
    fact: (positive) -> unsigned64.
    fact: (positive, unsigned64) -> unsigned64.
clauses
    fact(N) = fact(N, 1).

    fact(0, X) = X:- !.
    fact(N, X) = fact(N - 1, N * X).

    run():-
        write(fact(5)),
        _ = readLine().

Используем функции для вычисления чисел Фибоначчи. Последовательность Фибоначчи — это последовательность натуральных чисел, которая определяется следующим образом:

$$f(1) = f(2) = 1, f(n) = f(n – 1) + f(n – 2)$$ для $$n > 2$$.

Это определение можно буквально перенести в программу:

class predicates 
    f: (positive) -> unsigned64.
clauses
    f(N) = 1:- N < 3, !.
    f(N) = f(N - 1) + f(N - 2).

Но эта программа уже при n = 40 требует для поиска решения нескольких секунд. Поэтому используем для вычисления n-го числа Фибоначчи хвостовую рекурсию. Для этого будем хранить на каждом шаге рекурсии два соседних элемента последовательности.

class predicates
    fib: (positive) -> unsigned64.
    fib: (positive, unsigned64, unsigned64) -> unsigned64.
clauses
    fib(0) = 0:- !.
    fib(N) = fib(N, 0, 1).

    fib(1, _, Y) = Y:- !.
    fib(N, X, Y) = fib(N - 1, Y, X + Y).

    run():-
        write(fib(70)),
        _ = readLine().

Упражнение 2. Напишите программу, которая по заданному натуральному числу определяет номер наибольшего элемента последовательности Фибоначчи, не превосходящего этого числа.

5.3. Рекурсивный алгоритм

Рассмотрим задачу о ханойской башне. Эту задачу придумал Эдуард Люка в XIX веке. Задача заключается в следующем. Имеется три стержня — левый, средний и правый. На левом стержне находятся n дисков, диаметры которых попарно различны (рис. 5.2 (а)). Диски упорядочены по размеру диаметра, сверху лежит наименьший, снизу — наибольший. Требуется перенести диски с левого стержня на правый, используя средний стержень как вспомогательный. Переносить можно только по одному диску, при этом нельзя класть диск большего диаметра на диск меньшего диаметра.

Очевидно, что для того чтобы перенести нижний диск на правый стержень, нужно предварительно перенести башню, состоящую из n – 1 дисков, с левого стержня на средний стержень (рис. 5.2 (b)). После того, как нижний диск окажется на правом стержне (рис. 5.2 (c)), останется перенести башню со среднего стержня на правый стержень (рис. 5.2 (d)). Нетрудно показать, что оптимальное решение задачи с n дисками состоит из 2n – 1 перемещений дисков.

class predicates
    hanoi: (positive N, string Откуда, string ВспСтерж, string Куда).
clauses
    hanoi(0, _, _, _):- !.
    hanoi(N, A, B, C):-
        % перенос с A на B с помощью С
        hanoi(N - 1, A, C, B),
        writef("Перенести диск % с % на %\n", N, A, C),
        % перенос с B на C с помощью A
        hanoi(N - 1, B, A, C).

    run():-
        hanoi(3, "A", "B", "C"),
        _ = readLine().

Упражнения