Программирование на языке Пролог для искусственного интеллекта

       

Использование рекурсии



8. 2. 1.    Использование рекурсии

Этот принцип состоит в том, чтобы разбить задачу на случаи, относящиеся к двум группам:

(1)        тривиальные, или "граничные" случаи;
(2)        "общие" случаи, в которых решение получается из решений для (более простых) вариантов самой исходной задачи.

Этот метод мы использовали в Прологе постоянно. Рассмотрим еще один пример: обработка списка элементов, при которой каждый элемент преобразуется по одному и тому же правилу. Пусть это будет процедура

        преобрспис( Спис, F, НовСпиc)

где Спис - исходный список, F - правило преобразования (бинарное отношение), а НовСпиc - список всех преобразованных элементов. Задачу преобразования списка Спис можно разбить на два случая:

(1)        Граничный случай: Спис = [ ]

            Если Спис = [ ], то НовСпиc = [ ], независимо от F

(2)        Общий случай: Спис = [X | Хвост]

            Чтобы преобразовать список вида [X | Хвост], необходимо:

                        преобразовать список Хвост; результат - НовХвост;
                        преобразовать элемент Х по правилу F; результат - НовХ;
                        результат преобразования всего списка - [НовХ | НовХвост].

Тот же алгоритм, изложенный на Прологе:

        преобрспис( [ ], _, [ ]).

        преобрспис( [Х | Хвост], F, [НовХ | НовХвост] :-
                G =.. [F, X, НовХ],
                саll( G),
                пpeoбpcпиc( Хвост, F, НовХвост).

Одна из причин того, что рекурсия так естественна для определения отношений на Прологе, состоит в том, что объекты данных часто сами имеют рекурсивную структуру. К таким объектам относятся списки и деревья. Список либо пуст (граничный случай), либо имеет голову и хвост, который сам является списком (общий случай). Двоичное дерево либо пусто (граничный случай), либо у него есть корень и два поддерева, которые сами являются двоичными деревьями (общий случай). Поэтому для обработки всего непустого дерева необходимо сначала что-то сделать с его корнем, а затем обработать поддеревья.



Содержание раздела