|
По известному вам правилу доступности переменных (объектов), в теле подпрограммы доступны все переменные (объекты), объявленные в самой подпрограмме, а также переменные (объекты) объявленные во всех объемлющих блоках, в том числе и имя самой подпрограммы. Исключение составляет случай, когда переменная (объект) имеет такое-же имя как и переменная в объемлющем блоке и экранирует собой глобальную переменную.
Следствием правила о доступности переменных (объектов) является возможность вызова подпрограммой самой себя.
Процедуры и функции, производящие вызов "самих себя" называют рекурсивными.
Рекурсией называется ситуация, когда какая-то подпрограмма прямо или через другие подпрограммы вызывает себя в качестве подпрограммы. Реализуемый при этом алгоритм называется рекурсивным.
В математике очень часто встречаются последовательности чисел, в которых каждый следующий член выражается через предыдущие. В арифметической прогрессии, например, каждый следующий член равен предыдущему, увеличенному на разность прогрессии:
a{i} = a{i-1} + d.
Формулы, выражающие очередной член последовательности через один или несколько предыдущих членов, называют рекуррентными соотношениями.
Рассмотрим для примера функцию вычисления факториала n!. Как правило ее определяют как правило произведения первых n чисел натурального ряда
n!=1*2*3*…*n
Такое произведение можно легко вычислить с помощью итеративных конструкций (итерация ― это повторение), например, оператор цикла For
Procedure TForm1.Button1Click(Sender: TObject);
Var fact:Longint;
n,i:Integer;
Begin
n:=StrToInt(Edit1.Text); // Вводим n длявычисления n!
fact:=1;
For i:=1 to n do fact:=Fact*i;
Label1.Caption:='Факториал ' +IntToStr(n)+'! ='+IntToStr(fact);
End;
Однако существует другое определение факториала, в котором n! выражается через предыдущий (n-1)!, т.е. используется рекуррентная формула:
0!=1
для любого n>0 n!=n*(n-1)!
Наличие рекуррентного соотношения позволяет использовать рекурсию. Например, программа, использующая рекурсивную функцию для вычисления факториала n! имеет следующий вид:
Function fact(i:Integer):Longint;
Begin
If i=0 then fact:=1
else fact:=i*fact(i-1);
End;
Procedure TForm1.Button1Click(Sender:TObject);
Var n:Integer;
n:=StrToInt(n); // Вводим n длявычисления n!
Label1.Caption:='Факториал'+IntToStr(n)+'! ='+IntToStr(fact(n));
End;
Рассмотрим предложенный в предыдущем параграфе вариант программы «Родственные отношения». Определение - отношения предок в этой главе было таким:
предок(X,Z) :-родитель(Х,Z).
предок( X, Z) :-родитель( X, Y),предок( Y, Z).
Проанализируем некоторые варианты этой программы. Ясно, что все варианты будут иметь одинаковую декларативную семантику, но разные процедурные семантики.
В соответствии с декларативной семантикой Пролога мы можем, не меняя декларативного смысла, изменить порядок предложений в программе и порядок целей в телах предложений.
Процедура предок состоит из двух предложений, и одно из них содержит в своем теле две цели. Возможны, поэтому, четыре варианта данной программы, все с одинаковым декларативным смыслом. Эти четыре варианта можно получить, если поменять местами оба предложения и поменять местами цели в каждом из этих двух последовательностей предложений.
ЧИТАТЬ ДАЛЕЕ
| 
