Рекурсия. Рекурсивные подпрограммы (Turbo Pascal 7.0)

Рекурсия.

Рекурсивные подпрограммы

По известному вам правилу доступности переменных (объектов), в теле подпрограммы доступны все переменные (объекты), объявленные в самой подпрограмме, а также переменные (объекты) объявленные во всех объемлющих блоках, в том числе и имя самой подпрограммы. Исключение составляет случай, когда переменная (объект) имеет такое же имя как и переменная в объемлющем блоке и экранирует собой глобальную переменную. Следствием правила о доступности переменных (объектов) является возможность вызова подпрограммой самой себя.
Рекурсивные подпрограммы.
Процедуры и функции производящие вызов "самих себя" называют рекурсивными.
Рекурсия. Рекурсивный алгоритм.
Рекурсией называется ситуация, когда какая-то подпрограмма прямо или через другие подпрограммы вызывает себя в качестве подпрограммы. Реализуемый при этом алгоритм называется рекурсивным.
Рекуррентные соотношения.
В математике очень часто встречаются последовательности чисел, в которых каждый следующий член выражается через предыдущие. В арифметической прогрессии, например, каждый следующий член равен предыдущему, увеличенному на разность прогрессии:
a{i} = a{i-1} + d.
Формулы, выражающие очередной член последовательности через один или несколько предыдущих членов, называют рекуррентными соотношениями.
Рассмотрим для примера функцию вычисления факториала n!. Как правило её определяют как произведение первых n чисел натурального ряда
n! = 1*2*3*...*n
Такое произведение можно легко вычислить с помощью итеративных конструкций (итерация - это повторение), например, оператора цикла for
program ex_29_1;
var
Fact: Longint;
n, i: Integer;
begin
write (Введите число n: ); Readln(n);
Fact := 1;
for i:=1 to n do Fact := Fact*i;
Writeln(Факториал n! = , Fact);
end.
Однако сущетвует также другое определение факториала, в котором n! выражается чрез предыдущий (n-1)!, т.е. используется рекуррентная формула:
0! = 1
для любого n>0 n! = n*(n-1)!
Наличие рекуррентного соотношения позволяет использовать рекурсию. Например, программа, использующая рекурсивную функцию для вычисления факториала n! имеет следующий вид:
program ex_29_2;

var
n: integer;

function Fact(i: integer): longint;
begin
if i=0 then Fact:=1
else Fact:=i*Fact(i-1);
end;

begin
write(Введите число n: ); readln(n);
writeln(Факториал n! = , Fact(n));
end.
Чтобы понять, как она работает, вспомним, что на время выполнения подпрограммы вызывающая программа приостанавливается, а в оперативной памяти выделяется место для локальных переменных и параметров вызванной подпрограммы. Таким образом, при вызовах подпрограмм в оперативной памяти "накапливаются" приостановленные программы. При рекурсивных вызовах одной и той же функции Fact происходит то же самое, т.е. при каждом вызове функции Fact для её локальных переменных и параметров выделяются новые ячейки памяти. По завершению работы функции эти ячейки удаляются. Программы, в которых используются рекурсивные подпрограммы отличаются простотой, наглядностью и компактностью текста. Однако за эту простоту приходится расплачиваться неэкономным использованием оперативной памяти, так как выполнение рекурсивных подпрограмм требует значительно большего размера оперативной памяти во время выполнения, чем нерекурсивных. При каждом рекурсивном вызове для локальных переменных, а также для параметров подпрограмм, которые передаются по значению, выделяются новые ячейки памяти. В языке Turbo Pascal нет никаких ограничений на рекурсивные вызовы подпрограмм, необходимо только хорошо понимать, что каждый очередной рекурсивный вызов приводит к образованию новой копии локальных объектов подпрограммы и все эти копии, соответствующие цепочки активизированных и не завершенных рекурсивных вызовов, существуют независимо друг от друга. Для рассмотрения различных форм рекурсивных подпрограмм введём некоторые определения, имеющие отношение к рекурсии.
Глубина рекурсии.
Максимальное число рекурсивных вызовов подпрограммы без возвратов, которое происходит во время выполнения программы, называется глубиной рекурсии.
Текущий уровень рекурсии.
Число рекурсивных вызовов в каждый конкретный момент времени, называется текущим уровнем рекурсии.
Формы рекурсивных подпрограмм.
В общем случае любая рекурсивная подпрограмма (для примера назовём её Rec) включает в себя некоторое множество операторов S и один или несколько операторов рекурсивного вызова Р.
Главное требование к рекурсивным подпрограммам.
Главное требование к рекурсивным подпрограммам заключается в том, что вызов рекурсивной подпрограммы должен выполнятся по условию, которое на каком-то уровне рекурсии станет ложным. Если условие истинно, то рекурсивный спуск продолжается. Когда оно становится ложным, то спуск заканчивается и начинается рекурсивный возврат из всех вызванных на данный момент копий рекурсивной подпрограммы.
Существуют три разных формы рекурсивных подпрограмм:
1) Форма с выполнением действий до рекурсивного вызова (с выполнением действий на рекурсивном спуске).
procedure Rec;
begin
S;
if условие then Rec;
end;
2) Форма с выполнением действий после рекурсивного вызова (с выполнением действий на рекурсивном возврате).
procedure Rec;
begin
if условие then Rec;
S;
end;
3) Форма с выполнением действий как до, так и после рекурсивного вызова (с выполнением действий как на рекурсивном спуске так и на рекурсивном возврате.
procedure Rec;
begin
S1;
if условие then Rec;
S2;
end;
Все формы рекурсивных процедур находят применение на практике. Многие задачи, в том числе вычисление факториала, безразличны к тому, какая используется форма рекурсивной процедуры.
Рассмотренная в начале рекурсивная функция Fact, выполняет вычисление факториала на возврате.