Практика программирования (Бейсик, Си, Паскаль)



         

Глава 5.


Рекурсивные функции и процедуры

В простейшем варианте процедура (функция) считается рекурсивной, если она пытается вызвать сама себя. Математики нередко прибегают к рекурсивному определению функций:

n! = n*(n-1)!

Естественно, что при таком хождении "по кругу" должно быть предусмотрено условие выхода, иначе вычислительный процесс может продолжаться бесконечно долго. В примере с факториалом тело процедуры на Паскале может выглядеть следующим образом:

if n < 2 then fact:=l else fact:=n*fact(n-1);

В более сложных вариантах рекурсивная процедура входит в состав двух или более процедур, последняя из которых вновь обращается к начальной:

А -> В -> А -> В -> А ...

В язык Паскаль, требующий описать любой объект до его использования, пришлось включить специальное опережающее объявление рекурсивных процедур, сопровождаемое служебным словом forward:

{ Опережающее объявление первой в цепочке процедуры А }

procedure А(<список параметров>);

forward; { Описание последней в цепочке рекурсивной процедуры В }

procedure В(<список параметров>);

begin

А(...); { Вызов рекурсивной процедуры А }

end; { Описание первой в цепочке рекурсивной процедуры А }

procedure A; { Здесь можно не повторять список аргументов } begin

В (...); { Вызов рекурсивной процедуры В } end;

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

Р = =1;

for i:=l to n do p:=p*i;

fact:=p;

Однако, как бы ни относились разные программисты к рекурсии, следует признать, что некоторые рекурсивные программы выглядят очень эффектно и их алгоритмы оказываются намного более прозрачными (см., например, процедуру быстрой сортировки quicksort илиигровую программу "Ханойские башни").




Содержание    Вперед