|
Рекурсия, т. е. возможность ввести в определение объекта ссылку на сам объект, часто возникает в программировании. Рекурсия является одним из фундаментальных «концептуальных инструментов», имеющихся в распоряжении программиста. К сожалению, она освоена далеко не достаточно; многие программисты избегают простых рекурсивных решений. Рекурсивные механизмы и их конкретная реализация в Прологе заслуживает более отчетливого понимания.
Система обозначений, применяемая, в частности, для описания такого типа рекурсивных «синтаксических уравнений», известных под названием «форма Бэкуса - Наура», широко используется для синтаксического описания языков программирования, начиная с АЛГОЛа 60.
Рекурсивные определения могут также применяться в повседневной жизни. Например, самый простой способ точно определить родственное отношение между двумя людьми - это сказать, что X и Y являются родственниками:
- либо если Y- отец, мать, сын или дочь X (или супруг, если включить степень родства по браку);
- либо если существует некий Z, такой, что X является родственником Z, а Zявляется родственником Y.
Для выражения того же самого определения нерекурсивным способом потребовалось бы прибегнуть к понятию «цепочка родственных отношений» и ввести в определение длину такой цепочки.
Особым случаем рекурсивного определения является математическое понятие рекуррентного определения. Так, коэффициенты в треугольнике Паскаля (сочетания) могут быть определены двойной рекуррентностью.В этой главе нас интересуют рекурсивные подпрограммы, т.е. такие подпрограммы, текст которых содержит один или несколько вызовов самой подпрограммы (прямая рекурсивность), или, шире, подпрограммы, выполнение которых может привести к одному или нескольким вызовам самой подпрограммы. Такие подпрограммы могут непосредственно использоваться для установления, соответствует ли объект рекурсивному определению, как мы только что видели.
Рассмотрим следующий алгоритм. Предположим существование типа ЛИЧНОСТЬ; если для всякого X этого типа функция семья(X) дает список элементов его ближайших родственников (отец, мать, дети), то для определения, являются ли два человека родственниками, имеем программу:
программа родственники:
ЛОГ (аргументы X, Y: ЛИЧНОСТИ)
родственники = ложь;
для Z из семья(X) пока ~ родственники повторять
родственники = (Z =Y или родственники (Z,Y))
Отметим, что в последней строке имя «родственники» слева от знака = означает результат программы, а справа от стрелки означает, наоборот, результат рекурсивного вызова этой подпрограммы (оно отмечается курсивом). Эта строка означает, что X и Y являются родственниками тогда и только тогда, когда существует член Z семьи X, такой, что либо Z = Y, либо Z и Y являются родственниками.
Далее в этой главе мы приведем сначала несколько примеров рекурсивных алгоритмов, заимствованных из различных областей информатики; затем укажем, каким образом рекурсивные подпрограммы могут быть реализованы на языке программирования Пролог и при использовании языков более низкого уровня; введем понятие восходящего рекурсивного вычисления; наконец, изучим особо важный класс рекурсивных алгоритмов-алгоритмы последовательных испытаний.
|
