Прямая и косвенная рекурсия

Если подпрограмма P содержит явное обращение к самой себе, то она называется прямо рекурсивной.	Если подпрограмма P вызывает другую подпрограмму Q, которая, в свою очередь, прямо или косвенно вызывает Р, то Р называют косвенно рекурсивной.
procedure P; begin ¼ P ¼ end;	procedure P; begin ¼ Q ¼ end; procedure Q; begin ¼ P ¼ end;

Предварительное (опережающее) описание подпрограммы

При косвенной рекурсии две подпрограммы, например, P и Q, содержат взаимные вызовы друг друга. При компиляции процедуры P компилятор не может правильно обработать вызов процедуры Q, поскольку она описана ниже по тексту. Разрешить эту ситуацию позволяет предварительное (или опережающее) описание.

Предварительное описание – это заголовок подпрограммы, за которым следует ключевое слово forward вместо тела подпрограммы. Предварительное описание вызываемой процедуры Q дается раньше описания вызывающей процедуры P

procedure Q(список формальных параметров); forward; {Предварительное описание}

procedure P;

begin

… Q …

end;

procedure Q(список формальных параметров); {Полное описание вызываемой процедуры Q}

begin

… P …

end;

Опасности рекурсии

При применении рекурсивных алгоритмов следует избегать трех основных опасностей:

1) Бесконечной рекурсии.

2) Необоснованного применения рекурсии. Обычно это происходит, если алгоритм типа рекурсивного вычисления чисел Фибоначчи многократно вычисляет одни и те же промежуточные значения.

3) Глубокой рекурсии. Если алгоритм достигает слишком большой глубины рекурсии, он может привести к переполнению стека. Минимизировать использование стека можно за счет уменьшения числа определяемых в подпрограмме переменных, использования глобальных переменных. Если стек все равно переполняется, следует переписать алгоритм в нерекурсивном виде.

Бесконечная рекурсия

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

program Recur;

procedure Rec;

begin

{*} writeln(’Рекурсия');

{**}Rec

end;

begin Recend.

Теоретически программа будет бесконечно выводить строку ’Рекурсия' (вывод на рекурсивном спуске). Однако, если в процедуре Rec поменять местами оператор {*} вывода и оператор {**} вызова Rec, то она ничего не выведет, хотя теоретически будет работать бесконечно. Вывод должен выполняться на рекурсивном возврате, который никогда не произойдет из-за того, что рекурсивный вызов происходит безусловно.

В действительности из-за конечного размера памяти, выделяемой под стек вызовов подпрограмм, в конце концов произойдет переполнение этого стека, и программа будет аварийно остановлена.

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

Добавим в процедуру Rec параметр, который сначала равен максимальному числу рекурсивных вызовов, а при очередном рекурсивном вызове уменьшается на 1.

procedure Pec(n:integer);

begin

writeln(’Рекурсия');

if n>0 then Rec(n-1)

end;

После n вызовов значение n станет равным 0, и условие вызова перестанет выполняться.

Глубокая рекурсия

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

Если стек все равно переполняется, перепишите алгоритм в не рекурсивном виде.