Лекции.Орг


Поиск:




Категории:

Астрономия
Биология
География
Другие языки
Интернет
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Механика
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Транспорт
Физика
Философия
Финансы
Химия
Экология
Экономика
Электроника

 

 

 

 


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




Если подпрограмма 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 Rec end.

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

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

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

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

procedure Pec(n:integer);

begin

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

if n>0 then Rec(n-1)

end;

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

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

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

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





Поделиться с друзьями:


Дата добавления: 2016-11-12; Мы поможем в написании ваших работ!; просмотров: 866 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Если президенты не могут делать этого со своими женами, они делают это со своими странами © Иосиф Бродский
==> читать все изречения...

2507 - | 2379 -


© 2015-2025 lektsii.org - Контакты - Последнее добавление

Ген: 0.011 с.