Рекурсия

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

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

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

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

Математический аналог - математическая индукция.

Применяют, если основную задачу можно разделить на подзадачи, с такой же структурой и целями, как в основной задаче.

Подпрограммы, реализующие рекурсию называются рекурсивными.

Для понимания рекурсии можно представлять рекурсивный вызов как вызов другой подпрограммы.

Главное в рекурсивных программах – организация выхода из подпрограммы в нужный момент. Иначе, выход из допустимого диапазона или переполнение памяти (аналог психическое растройство).

Различают 2 формы рекурсии: прямую и косвенную.

При прямой рекурсии процедура содержит оператор обращения к самой себе: А->А.

При косвенной рекурсии одна процедура вызывает другую, которая сама либо посредством других процедур вызывает исходную процедуру: А->В->А.

Другой вариант косвенной рекурсии, когда первая подпрограмма вызывает вторую, которая в момент вызова еще не определена. Для реализации используется предварительное описание процедур и функций.

Предварительное описание состоит из заголовка процедуры и следующего за ним зарезервированного слова Forward.

Классический пример рекурсивной функции в математике: вычисление факториала, возведение числа в целую степень.

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

Опасайтесь: бесконечной рекурсии (должно быть надежное условие остановки); глубокой рекурсии(память заполняется со скоростью , де N-глубина рекурсии); неуместного применения;

Вывод: рекурсию следует применять тогда, когда алгоритм с применением рекурсии значительно упрощает программу.

РЕКОМЕНДАЦИИ: Необходимо по возможности избегать применения рекурсии, так как большая глубина рекурсивных вызовов часто приводит к переполнению стека. В некоторых случаях проблему можно устранить, установив новый размер стека от 1024 до 65520 байт с помощью директивы {$M размер стека, нижняя граница, верхняя граница памяти}

Пример. Простейшая рекурсия (зацикленная).
Program DemoRecurs;
 Uses Crt;

Procedure PrintA;
begin
 writeln('Рекурсия');
 PrintA; {Процедура вызывает себя}
end;

Begin
 PrintA {Стартовый вызов процедуры}
end.
Пример. Вычисление факториала.
Program Factorial;
 Var F,N:integer;

Procedure FACT(N:integer; Var F:integer);
 begin
 IF N=0 THEN F:=1 {условие завершения}
 ELSE
 begin
 FACT(N-1,F); {самовызов}
 F:=N*F {вычисление F по рекурсивному F}
 end
 end;

Begin
 Write('Введите число= '); 
 Readln(N);
 FACT(N,F); {стартовый вызов}
 Writeln(F); {конечный результат}
 Readln
End.
Пример. Неправильный вызов процедуры.
Program DemoForward;
 Uses Crt;
 var A:integer;

Procedure P1(var T:real);
begin
 P2; {вызов Р2, а она не описана}
end;

Procedure P2(var V:real);
begin
 P1
end;

Begin
 P1; {стартовый вызов}
end.
Пример. Косвенная рекурсия.
Program DemoForward;
 Uses Crt;

Procedure P2 (формал.парам.); Forward; {предварит.описание}

Procedure P1;
 begin
 P2(факт.парам.)
 end;
Procedure P2; {список форм. парам. не повторяется}
 begin
 P1
 end;

Begin
P1
end.
Пример. Вычислить N-е число Фиббоначчи.
program Fib; 
 var n:byte;
 function F(k:byte):word; 
 begin 
 if k<2 then F:=1 else F:=F(k-1)+F(k-2); {рекурсивный вызов} 
 end; 
begin 
 write('введите номер числа Фиббоначчи'); 
 readln(N); 
 writeln(N,'-е число Фиббоначчи =',F(N)); 
 readln 
end.
Онлайн всего: 3
Гостей: 3
Пользователей: 0

STUDLAB Сообщить про опечатку на сайте