Рекурсии

ОБЛАСТЬ ДЕЙСТВИЯ ПАРАМЕТРОВ.

При создании программ, использующих процедуры, следует учитывать, что все объекты (метки, константы, типы, переменные, процедуры и функции), которые описываются после заголовка процедуры, называются локальными объектами и доступны только в пределах этой процедуры, но недоступны вызывающей программе. Все эти объекты создаются при входе в процедуру и уничтожаются при выходе из нее. Если одно и то же имя определено в нескольких процедурах, вызываемых одной и той же программой, то в каждой процедуре этому имени соответствует свой локальный объект.

Все объекты, описанные в вызывающей программе, называются глобальными и являются доступными внутри процедур, вызываемых этой программой. Поэтому обмен данными между программой и вызываемой ею процедурой может производиться и через глобальные переменные. Если одно и то же имя определено и в программе, и в вызываемой ею процедуре, то ему соответствует глобальный объект, но внутри процедуры глобальный объект недоступен, он как бы экранируется (маскируется) локальным объектом с таким же именем.

В Turbo Pascal допускается любой уровень вложенности процедур и функций. Процедура, описанная в основной программе, может иметь описания внутренних процедур и функций и т.д. При этом объекты, описанные в вызывающей процедуре, являются глобальными по отношению к вызываемой процедуре.

Для доступа к объектам, описанным в различных блоках, требуется соблюдение следующих правил:

1. Имена объектов, описанных в некотором блоке, считаются известными в пределах данного блока, включая и все вложенные блоки.

2. Имена объектов, описанных в блоке, должны быть уникальны в пределах данного блока и могут совпадать с именами объектов из других блоков.

3. Если в некотором блоке описан объект, имя которого совпадает с именем объекта, описанного в объемлющем блоке, то это последнее имя становится недоступным в данном блоке (оно как бы экранируется одноименным объектом данного блока).

Иногда при вызове подпрограмм-функций возникают побочные эффекты, выражающиеся в том, что вносятся нежелательные изменения в значения глобальных переменных. Поэтому надо быть внимательным при описании параметров-переменных, при выборе имен учитывать наличие глобальных объектов с такими именами.

Рекурсия – это такой способ организации вычислительного процесса, при котором процедура или функция в ходе выполнения составляющих ее операторов обращается сама к себе. Суть заключается в том, что при каждом вызове создается новая копия со своими переменными, но как только она завершает свою работу, то память, занятая этими локальными переменными, освобождается, а полученные результаты передаются в точку вызова.

Пример 6: Вычислить факториал натурального числа. Для того, чтобы вычислить N!, надо знать значение (N-1)! и умножить его на N, при этом 1!=1. В общем виде это можно записать так:

Решение:

program pr6;

var n,f:integer;

function fact(n:integer):integer;

begin

if n=1 then fact:=1

else fact:=n*fact(n-1)

end;

begin

writeln(‘Ввести число n>1’);

read(n);

f:=fact(n);

writeln(‘Для числа ‘,n,’ значение факториала =’,f)

end.

Пусть n=5, т.е. вычислить 5! Как же будет вычисляться факториал этого числа? Первый вызов этой функции будет из основной программы. Надо заметить, что при каждом обращении к функции будет появляться свой набор локальных переменных со своими значениями, в данном случае – переменная n, для которых выделяется память. А после завершения работы эта часть памяти освобождается, и переменные удаляются.

Так как n, то пойдем по ветке else и fact присваиваем значение n*fact(n-1), т.е. надо умножить 5 на значение функции fact(4). Поэтому обращаемся второй раз к этой же функции, но передаем ее новое значение параметра – 4. Так делаем до тех пор, пока не передадим значение равное 1. Тогда n=1, а поэтому значение функции fact:=1. Таким образом, n=1 – это условие, по которому процесс входа в следующую рекурсию заканчивается. Идет возвращение в точку возврата и подстановка в оператор присваивания значения вычисленной функции. Т.е. возвращаемся в предыдущую функцию для n=2: fact:=n*fact(n-1), значит, fact:=2*1, следовательно, fact(2)=2. И возвращаемся дальше. Таким образом, получаем значение fact(5)=120, это значение и присваивается переменной f.

Итак, при выполнении рекурсивной подпрограммы осуществляется многократный переход от некоторого текущего уровня организации алгоритма к нижнему уровню последовательно до тех пор, пока, наконец, не будет получено тривиальное решение поставленной задачи. В данном примере решение при n=1 тривиально, т.е. fact=1. Затем осуществляется возврат на верхний уровень с последовательным вычислением значения функции fact.

Следует отметить, что использование рекурсивной формы организации алгоритма обычно выглядит изящнее итерационной и дает более компактный текст программы, но при выполнении, как правило, медленнее и может вызвать переполнение стека. Это объясняется тем, что при каждом входе в подпрограмму ее локальные переменные размещаются в особым образом организованной области памяти, называемой программным стеком.