считается рекурсивной, если она пытается
Рекурсивные функции и процедуры
В простейшем варианте процедура (функция) считается рекурсивной, если она пытается вызвать сама себя. Математики нередко прибегают к рекурсивному определению функций:
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 илиигровую программу "Ханойские башни").
