Рекурсивной называется подпрограмма, в которой содержится обращение к самой себе. Такая рекурсия называется прямой. Есть также косвенная рекурсия, когда две или более подпрограмм вызывают друг друга.
При обращении подпрограммы к самой себе происходит то же самое, что и при обращении к любой другой функции или процедуре: в стек записывается адрес возврата, резервируется место под локальные переменные, выполняется передача параметров, после чего управление передается первому исполняемому оператору подпрограммы.
Для завершения вычислений каждая рекурсивная подпрограмма должна содержать хотя бы одну ветвь алгоритма, заканчивающуюся возвратом в вызывающую программу.
_ 4.4. Средства организации модульности в языках высокого уровня Простой пример рекурсивной функции — вычисление факториала. Чтобы получить значение факториала числа п, требуется умножить на п-факториал числа (п -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;
Рассмотрим, что происходит при вызове этой функции при п = 3.
В стеке отводится место под параметр п, ему присваивается значение 3, и начинается выполнение функции. Условие в операторе if ложно, поэтому управление передается на ветвь else. Для вычисления выражения п • fact (п — 1) требуется повторно вызвать функцию fact.
Для этого в стеке отводится новое место под параметр п, ему присваивается значение 2, и выполнение функции начинается сначала. В третий раз функция вызывается со значением параметра, равным 1, и вот тут-то становится истинным выражение (п = 0) or (n = 1), поэтому происходит возврат из подпрограммы в точку вызова, т. е. на выражение п • fact (п — 1) для п = 2. Результат выражения присваивается имени функции и передается в точку ее вызова, т. е. в то же выражение, только теперь происходит обращение к параметру п, равному 3.
Достоинством рекурсии является компактная запись, а недостатками —расход времени и памяти на повторные вызовы функции и передачу ей параметров, а главное, опасность переполнения стека.
