Рекурсивные процедуры и функции. Примеры применения.
Паскаль допускает обращение функции внутри её определения (прямая рекурсия), либо обращение друг к другу двух или более определяемых функций – процедур (косвенная рекурсия).
Многие алгоритмы и структуры данных рекурсивно формируются просто. В частности, графы и деревья просто определяются рекурсивно и соответственно этому функции их обработки.
Граф называется деревом, если он имеет вид:
- вершина.
- деревья
Пример: Рекурсивный вариант обхода дерева.
procedure Print(root:pNode);
begin
if root<>nil then
begin
write(root^.info);
print(root^.left);
print(root^.right);
end;
end;
КЛП-обход, в случае дерева-выражения получим префиксную запись выражения.
Аналогично можно получить ЛПК и другие порядки, например, инфиксную и постфиксную записи выражения.
Рекурсивная версия задачи о вычислении:
function ExpVal(root:pNode;VarVal:tVarVal):integer;
begin
if term(root) then result:=TermVal(root);
else begin
result_1:=ExpVal(root^.left,VarVal);
result_2:=ExpVal(root^.right,VarVal);
result:=AtomVal(root^.info,result_1,result_2);
end;
end;
Поиск в дереве.
procedure Poisk(root:pNode;x:tInfo;var found:boolean;var pt:pNode);
begin
found:=false;
if root^.info=x then
begin
found:=true;
pt:=root;
end
else if root^.left<>nil then Poisk(root^.left,x,found,pt)
else if not found and root^.right<>nil then
Poisk(root^.right,x,found,pt);
end;
end;
Поиск в дереве поиска:
procedure Poisk(root:pNode;x:tInfo;var found:boolean;var pt:pNode);
begin
if root=nil then found:=false
else if root^.info=x then
begin
found:=true;
pt:=root;
end
else if x<root^.info then Poisk(root^.left,x,found,pt)
else Poisk(root^.right,x,found,pt);
end;
Пример с факториалом:
1, n=0
fact(n)=
fact(n-1)*n, n>0
function fact(n integer):longint;
begin
if n=0 then fact:=1
else fact:=n*fact(n-1);
end;
Проблемы с семантикой рекурсии.
В случае не рекурсивных вызовов семантика обращений строилась с помощью замены обращения модифицированным телом процедуры. Фактически мы описывали её (семантику) как построение некоторого выражения – программы на базовом Паскале. Этот способ работал и для кратных обращений.
Использование процедуры процедурой:
P P1 P2
Чётко
выделялись два этапа:
1) Построение выражения;
2) Его вычисление.
В этом случае такое дерево не может быть построено.
Вспомним алгоритм вычисления выражения. Как показал наш анализ, для того, чтобы вычислить значение выражения, необязательно строить его полностью. Более того, мы не обязаны для этого обходить всё дерево.
Пример: Если значение левого терма – ноль, а операция у нас – умножение, то значение правого терма вычислять не нужно.
Любая рекурсия связана с последовательным построением и вычислением выражения. Действительно, в любом случае можно считать, что рекурсивный вызов выполняется в случае истинности некоторого условия. При каждом рекурсивном вызове вычисляется выражение, и дерево достраивается лишь в случае его истинности.
Таким образом, любой рекурсивный алгоритм эквивалентен построению и обходу некоторого дерева.
P1
P1 P2 P1 P2 P2
1 2 B1+
B2+
if B1
then P1 if
B2
then P2
1 2 2
B1+ B2+ B2+
В случае двух вызовов получаем бинарное дерево.
КЛП-обход или стековый обход.
Описали семантику рекурсии с помощью циклов. Теоретически возможно описание семантики циклов через рекурсию.
s, B(s)=false
while B do S(s)
S, while B do S, B(s)=true
Теоретически можно программировать без циклов в терминах лишь рекурсии.
Функциональным программированием называется программирование в терминах рекурсивного определения функций. Логическим программированием: языки основаны на рекурсивном определении булевых функций (предикатов).