Алгоритм, в котором предусмотрен вызов подпрограммой себя самой, называется рекурсивным. Использовать эту особенность в Pascal могут как процедуры, так и функции.
Количество обращений произведенных подпрограммой без возвращения в основную часть называется глубиной рекурсии.
В ЯП Pascal глубина рекурсии не ограничена, но необходимо предусмотреть условие, на каком-либо шаге приводящее к завершению вызова процедурой или функцией самой себя. Иначе произойдет зацикливание.
Рассмотрим функцию, рекурсивно рассчитывающую значение числа Фибоначчи, номер которого вводиться с клавиатуры.
|
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
program recursio;
uses crt; var n: shortint; function Fibonacci(p_n: shortint): longint; begin if (p_n=1) then Fibonacci:=0 else if (p_n=2) then Fibonacci:=1 else Fibonacci:=Fibonacci(p_n—1)+Fibonacci(p_n—2) end; begin clrscr; write(‘ Номер числа: ‘); readln(n); write(‘ Значение чиса: ‘, Fibonacci(n)); end. |
Во время выполнения рекурсивной подпрограммы в оперативной памяти выделяется место для данных вызванной процедуры или функции. И те подпрограммы, которые рекурсивно передают управление, остаются в оперативной памяти. Поэтому завершение подпрограмм происходит пошагово, в обратном порядке.
Вот еще один пример работы рекурсивного метода. Программа вычисляет сумму цифр числа, заданного пользователем.
|
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
program recursio;
uses crt; var n: integer; function Sum(p_n: integer): integer; var r: integer; begin r:=p_n mod 10; if (p_n div 10)<>0 then r:=r+Sum(p_n div 10); Sum:=r; end; begin clrscr; write(‘ Число: ‘); readln(n); if Sum(n)>=0 then write(‘ Сумма цифр : ‘, Sum(n)) else write(‘ Сумма цифр: ‘, Sum(n)*(—1)); end. |
Рекурсия в подпрограммах визуально оптимизирует код, но как уже было сказано ранее, такие алгоритмы несут сильную нагрузку на оперативную память. Поэтому приходиться выбирать между компактностью и производительностью.