6. Рекурсии.

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

Пример 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.

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