Рекурсией называется прямое или косвенное обращение подпрограммы к самой себе. Подпрограмма, которая вызывает саму себя, называется рекурсивной.
При выполнении правильно организованной рекурсивной подпрограммы осуществляется многократный переход от некоторого текущего уровня организации алгоритма к нижнему уровню последовательно до тех пор, пока, наконец, не будет получено тривиальное решение поставленной задачи. В примере 8.5 решение при N = 0 тривиально и используется для остановки рекурсии.
Пример 8.5:
Function Fac(n: Integer): Real;
begin
if n < 0 then
WriteLn ('n не может быть <0!!!')
else
if n = 0 then
Fac := 1
else
Fac := n * Fac(n-l)
end ; {Fac}
Рекурсивный вызов может быть косвенным. В этом случае подпрограмма обращается к себе опосредованно, путем вызова другой подпрограммы, в которой содержится обращение к первой, например:
Procedure A (i : Byte) ;
begin
.......
В (i);
.......
end ;
Procedure В (j : Byte) ;
.......
begin
.......
A(j);
.......
end;
При любом вызове подпрограммы в память компьютера заносится следующая информация:
- текущие значения параметров, передаваемых через значение;
- местонахождение (адреса) параметров переменных;
- адрес возврата, т.е. адрес оператора, который следует за оператором вызова.
Таким образом, при рекурсивном вызове занимаемая область памяти увеличивается очень быстро, что ведет к риску переполнения памяти компьютера. Этого можно избежать путем замены рекурсии на итерацию.
Рекурсию необходимо использовать в случаях, когда написание нерекурсивных алгоритмов является очень сложным: перевод программ на языке ТУРБО ПАСКАЛЬ на язык компьютера, машинная графика, распознавание образов и т.д.
