Использование рекурсии
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, НовХвост).
Одна из причин того, что рекурсия так естественна для определения отношений на Прологе, состоит в том, что объекты данных часто сами имеют рекурсивную структуру. К таким объектам относятся списки и деревья. Список либо пуст (граничный случай), либо имеет голову и хвост, который сам является списком (общий случай). Двоичное дерево либо пусто (граничный случай), либо у него есть корень и два поддерева, которые сами являются двоичными деревьями (общий случай). Поэтому для обработки всего непустого дерева необходимо сначала что-то сделать с его корнем, а затем обработать поддеревья.
