Рекурсия
Рекурсия - вычислительный процесс, в котором программа (или подпрограмма) обращается сама к себе. Примеры рекурсии: отражение в системе зеркал, дерево-ветки, сон во сне, мозаика в калейдоскопе, геометрические рисунки, рекурсивные ландшафты.
Рекурсия вызывает психолингвистический эффект. Ее восприятие человеком всегда сопровождается чувством тревоги и даже страха. Чем больше глубина рекурсивной вложенности, тем сильнее тревога.
Хотя рекурсия упрощает понимание некоторых явлений, люди обычно мыслят нерекурсивно. Все стремятся разбить сложные задачи на подзадачи меньшего объема, которые можно выполнить по порядку одна за одной до полного завершения.
Блез Паскаль представлял природу как рекурсивную, везде повторяющуюся сферу. Ему принадлежит определение: "Природа-это бесконечная сфера, центр которой везде, а окружность нигде". В черновике сохранилась запись – "устрашающая сфера". В современных фильмах ужасов часто эксплуатируется понятие рекурсии, когда появляются повторящиеся вложенные образы : арки, зеркала, винтовые лестницы, вложенные пространства и т.п.
Математический аналог - математическая индукция.
Применяют, если основную задачу можно разделить на подзадачи, с такой же структурой и целями, как в основной задаче.
Подпрограммы, реализующие рекурсию называются рекурсивными.
Для понимания рекурсии можно представлять рекурсивный вызов как вызов другой подпрограммы.
Главное в рекурсивных программах – организация выхода из подпрограммы в нужный момент. Иначе, выход из допустимого диапазона или переполнение памяти (аналог психическое растройство).
Различают 2 формы рекурсии: прямую и косвенную.
При прямой рекурсии процедура содержит оператор обращения к самой себе: А->А.
При косвенной рекурсии одна процедура вызывает другую, которая сама либо посредством других процедур вызывает исходную процедуру: А->В->А.
Другой вариант косвенной рекурсии, когда первая подпрограмма вызывает вторую, которая в момент вызова еще не определена. Для реализации используется предварительное описание процедур и функций.
Предварительное описание состоит из заголовка процедуры и следующего за ним зарезервированного слова Forward.
Классический пример рекурсивной функции в математике: вычисление факториала, возведение числа в целую степень.
При выполнении правильно организованного рекурсивного блока осуществляется многократ-ный последовательный переход от некоторого текущего уровня организации алгоритма к нижнему уровню до тех пор, пока не будет найдено условие, при котором рекурсия останавливается.
Опасайтесь: бесконечной рекурсии (должно быть надежное условие остановки); глубокой рекурсии(память заполняется со скоростью , де N-глубина рекурсии); неуместного применения;
Вывод: рекурсию следует применять тогда, когда алгоритм с применением рекурсии значительно упрощает программу.
РЕКОМЕНДАЦИИ: Необходимо по возможности избегать применения рекурсии, так как большая глубина рекурсивных вызовов часто приводит к переполнению стека. В некоторых случаях проблему можно устранить, установив новый размер стека от 1024 до 65520 байт с помощью директивы {$M размер стека, нижняя граница, верхняя граница памяти}
Пример. Простейшая рекурсия (зацикленная).
Рекурсия вызывает психолингвистический эффект. Ее восприятие человеком всегда сопровождается чувством тревоги и даже страха. Чем больше глубина рекурсивной вложенности, тем сильнее тревога.
Хотя рекурсия упрощает понимание некоторых явлений, люди обычно мыслят нерекурсивно. Все стремятся разбить сложные задачи на подзадачи меньшего объема, которые можно выполнить по порядку одна за одной до полного завершения.
Блез Паскаль представлял природу как рекурсивную, везде повторяющуюся сферу. Ему принадлежит определение: "Природа-это бесконечная сфера, центр которой везде, а окружность нигде". В черновике сохранилась запись – "устрашающая сфера". В современных фильмах ужасов часто эксплуатируется понятие рекурсии, когда появляются повторящиеся вложенные образы : арки, зеркала, винтовые лестницы, вложенные пространства и т.п.
Математический аналог - математическая индукция.
Применяют, если основную задачу можно разделить на подзадачи, с такой же структурой и целями, как в основной задаче.
Подпрограммы, реализующие рекурсию называются рекурсивными.
Для понимания рекурсии можно представлять рекурсивный вызов как вызов другой подпрограммы.
Главное в рекурсивных программах – организация выхода из подпрограммы в нужный момент. Иначе, выход из допустимого диапазона или переполнение памяти (аналог психическое растройство).
Различают 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.
