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

Рекурсивной называется подпрограмма, в которой содержится обращение к самой себе. Такая рекурсия называется прямой. Есть также косвеннаярекурсия, когда две или более подпрограмм вызывают друг друга.

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

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

Простой пример рекурсивной функции — вычисление факториала (это не означает, что факториал следует вычислять именно так). Чтобы получить факториал числа n, требуется умножить на nфакториал (n– 1)!. Известно также, что 0! = 1 и 1! = 1.

function fact(n : byte) : longint;

begin

if (n = 0) or (n = 1) then fact := 1

else fact := n * fact(n – 1);

end;

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

Достоинствомрекурсии является компактная запись. К недостаткамотносятся расход времени и памяти на повторные вызовы функции и передачу ей параметров, а главное, опасность переполнения стека.