Рекурсия

Содержание и мощность рекурсивного определения, а также его главное назначение, состоит в том, что оно позволяет с помощью конечного выражения определить бесконечное множе­ство объектов. Аналогично, с помощью конечного рекурсивного алгоритма можно определить бесконечное вычисление, причем ал­горитм не будет содержать повторений фрагментов текста.

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

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

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

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

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

В общем случае любая рекурсивная процедура Rec включает в себя некоторое множество операторов S и один или несколько операторов рекурсивного вызова.

Безусловные рекурсивные процедуры приводят к бесконечным процессам, и на эту проблему нужно обратить особое внимание, так как практическое использование процедур с бесконечным са­мовызовом невозможно.

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

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

1) форма с выполнением действий до рекурсивного вызова (на
рекурсивном спуске);

procedure Rec; begin

S;

if условие then Rec; end;

2) форма с выполнением действий после рекурсивного вызова
(на рекурсивном возврате);

procedure Rec; begin

if условие then Rec;

S; end;

3) форма с выполнением действий как до, так и после рекур­сивного вызова (с выполнением действий как на рекурсивном спуске, так и на рекурсивном возврате).

procedure Rec; begin

S1;

if условие then Rec; S2; end;

Все формы рекурсивных процедур находят применение на практике. Многие задачи, в том числе вычисление факториала, без­различны к тому, какая используется форма рекурсивной процеду­ры. Однако есть классы задач, при решении которых программисту требуется сознательно управлять ходом работы рекурсивных про­цедур и функций. Такими, в частности, являются задачи, исполь­зующие списковые и древовидные структуры данных.

Дата добавления: 2014-12-16