![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Понятие рекурсии
Рекурсия (от латинского recursio - возвращение) - это такой способ организации вычислительного процесса, при котором процедура или функция в ходе выполнения составляющих ее операторов обращается сама к себе.
Для того, чтобы такое обращение не было бесконечным, в тексте подпрограммы должно быть условие, по достижению которого дальнейшего обращения не происходит. таким образом, рекурсивное обращение может включаться только в одну из ветвей подпрограммы.
В языке Паскаль нет никаких ограничений на рекурсивные вызовы подпрограмм, необходимо только понимать, что каждый очередной рекурсивный вызов приводит к образованию новой копии локальных объектов подпрограммы и все эти копии, соответствующие цепочке активизированных и не завершенных рекурсивных вызовов, существуют независимо друг от друга
Рекурсия достаточно широко применяется в программировании, что основано на рекурсивной природе многих математических алгоритмов. А также Вы должны знать, что любой рекурсивный алгоритм можно преобразовать в эквивалентный итеративный (то есть использующий циклические конструкции).
В больших и сложных программах иногда приходится заменять рекурсию на итерацию. Дело в том, что рекурсия связана с многократными вызовами процедур, а это несколько менее эффективно при выполнении по сравнению с использованием циклов. Однако рекурсивные версии программ, как правило, гораздо короче и нагляднее.
Хорошей иллюстрацией механизма рекурсии является функция для вычисления факториала натурального числа. Вспомним, что факториалом числа называется произведение всех натуральных чисел от 1 до этого числа включительно:
N! = 1*2*3*... *(N-2)*(N-1)*N
1! = 1
0! = 1
Сначала покажем обычную не рекурсивную функцию для вычисления факториала, которая реализует итеративный алгоритм вычисления:
Function NonRecFact(N:integer): LongInt;
Var
i: integer; {переменная цикла }
Res: LongInt; {результат}
Begin
Res:= 1;
for i:= 1 to N do
res:= Res*i;
NonResFact:= Res;
End;
Вторая функция использует рекурсивные обращения, что делает ее гораздо компактнее, и основана на очевидном соотношении:
N! = (N-1)!*N
Иными словами, чтобы получить значение факториала от числа N, достаточно умножить на N значение факториала от предыдущего числа:
Function RecFact(N:integer): LongInt;
Begin
if N <= 1
then
ResFact:= 1
else
ResFact:= N*ResFact(N-1);
End;
Полностью программа, вычисляющая факториал числа, будет выглядеть так:
Program Rekurs;
Var
N: integer;
F: Longint;
{ - - - - - - - - - - - - - - - - - - - -}
Function RecFact(N:integer): LongInt;
Begin
if N <= 1
then
ResFact:= 1
else
ResFact:= N*ResFact(N-1);
End;
{ - - - - - - - - - - - - - - - - - - - -}
Begin
writeln('Введите число N > ';
read(N);
F:= RecFact(N);
writeln('Для числа ',N,' значение факториала равно ',F);
End.
После запуска программы на экран выводится запрос "Введите число N > ", затем с клавиатуры считывается введенное значение и в выражении F:=RecFact(N) вызывается функция RecFact с параметром-значением N. В подпрограмме-функции проверяется условие N<=1. Если оно выполняется, то функции ResFact присваивается значение 1 и на этом выполнение подпрограммы завершается. Если условие N<=1 не соблюдается, то выполняется вычисление произведения N*ResFact(N-1). Вычисление произведения носит рекурсивный характер, так как при этом осуществляется вызов функции ResFact(N-1), значение которой вычисляется, в свою очередь, через вызов функции ResFact, параметром которой также будет функция ResFact, и т.д., до тех пор пока значение формального параметра N не будет равно 1. Так как базовая часть описания рекурсивной функции ResFact определяет значение ResFact для N=1, равным единице, то рекурсивные вызовы функции ResFact больше не выполняются, а наоборот выполняется вычисление функции ResFact для чисел, возрастающих от 1 до N, причем функция ResFact всякий раз возвращает значение, равное произведению очередного числа на факториал от предыдущего числа. Последнее возвращение результата вычисления функции ResFact присвоит переменной F значение произведения всех чисел от 1 до N, т.е. факториал числа N.
Итак, при выполнении рекурсивной подпрограммы осуществляется многократный переход от некоторого текущего уровня организации алгоритма к нижнему уровню последовательно до тех пор, пока не будет получено тривиальное решение поставленной задачи. В нашем примере решение при N=1 тривиально, т.е. ResFact=1. Затем осуществляется возврат на верхний уровень с последовательным вычислением значения функции ResFact.
Задание. Введите текст рассмотренной выше программы и запишите файл на диск под соответствующим именем, а затем откомпилируйте его. После того, как компиляция закончится успешно, задайте для просмотра в окне отладчика переменные N, F. Установите видимыми одновременно окна редактора с текстом программы и окно просмотра. Исполните программу в пошаговом режиме с заходом в функцию и пронаблюдайте за изменением значения переменной N при рекурсивных вызовах функции ResFact.
Задание. Напишите программы, демонстрирующие выполнение рекурсивного и итеративного алгоритма для задач:
Примеры задач рекурсивного решения в текстовом и графическом режимах | ||
Задача 1. Нахождение n-го члена арифметической прогрессии
(an=a1+d*(n-1)-формула n-го члена арифметической прогрессии).
Program Progressiy;
Var
a1, d, k: real;
n: integer;
{ - - - - - - - - - - - - - - - - - - - -}
Function Arif (a1, d: real; n: integer): real;
Begin
if n = 1
then
Arif:= a1
else
Arif:= Arif(a1, d, n - 1) + d;
End;
{ - - - - - - - - - - - - - - - - - - - -}
Begin
writeln('Задайте первый член прогрессии');
readln(a1);
writeln('Задайте разность арифметической прогрессии');
readln(d);
writeln('Арифметическая прогрессия ', Аrif(a1, d, n): 4: 2);
End.
Задание. Составьте программу
a) нахождения n-го члена геометрической прогрессии,
б) нахождения суммы членов арифметической прогрессии,
в) нахождения суммы членов геометрической прогрессии,
г) нахождения n-го члена ряда Фибоначчи.
Задача 2. Вложенность квадратов.
Program KaparovS;
Uses
Crt, Graph;
Var
x, y, x1, y1, x2, y2, x3, y3, n, d, a, b: integer
{ - - - - - - - - - - - - - - - - - - - -}
Procedure Pic(x, y, x1, y1, x2, y2, x3, y3, n, d: integer);
Var
k, j: integer;
Begin
if n >=1
then
begin
Line(x, y, x1, y1);
Line(x1, y1, x2, y2);
Line(x2, y2, x3, y3);
Line(x3, y3, x, y);
j:= x;
k:= y;
x:= (x1-x) div 2 + x;
y:= (y1-y) div 2 + y;
x1:= (x2-x1) div 2 + x1;
y1:= (y2-y1) div 2 + y1;
x2:= (x3-x2) div 2 + x2;
y2:= (y3-y2) div 2 + y2;
x3:= (j-x3) div 2 + x3;
y3:= (k-y3) div 2 + y3;
Pic(x, y, x1, y1, x2, y2, x3, y3, n-1, d);
end;
End;
{ - - - - - - - - - - - - - - - - - - - -}
Begin
ClrScr;
write ('Введите количество повторений: ');
readln (n);
x:= 0;
y:= 0;
x1:= 400;
y1:= 0;
x2:= 400;
y2:= 400;
x3:= 0;
y3:= 400;
a: Detect;
InitGraph(a, b, 'D:\TP7\BGI');
ClearDevice;
Setcolor(Green);
Pic(x, y, x1, y1, x2, y2, x3, y3, n, d);
readln;
CloseGraph;
End.
Задание. Наберите программу и просмотрите ее действие. Дополните программу комментарием. По желанию улучшите алгоритм.
Творческое задание. Придумайте и решите задачу на демонстрацию рекурсии в графическом режиме.
Косвенная рекурсия. | ||
Рассмотренные выше программы использовали так называемую прямую рекурсию, когда в теле некоторой процедуры содержался непосредственный вызов самой себя. В языке Паскаль допускается также и косвенная рекурсия, когда, например, процедура, процедура А вызывает процедуру В, а та, в свою очередь,- процедуру А. Длина таких цепочек вызовов может быть произвольной, однако при разработке программы необходимо тщательно следить за тем, чтобы рекурсивный алгоритм был сходимым, то есть не приводил к бесконечным взаимным вызовам подпрограмм.
Образно косвенную рекурсию можно описать так. Перед зеркалом 1 стоит зеркало 2, в котором отражается само зеркало 1. В последнем видно зеркало 2 и т.д.
Приведем пример программы, иллюстрирующей косвенные рекурсивные вызовы процедур. В этой программе процедуры Rec1 и Rec2 рекурсивно вызывают друг друга, поочередно уменьшая свои фактические параметры. Легко видеть, что обе процедуры работают с одной глобальной переменной А, которая передается в них по ссылке. Критерием завершения работы является обращение этой переменной в ноль.
Обратите внимание, что в программе необходимо предварительное определение второй процедуры Rec2, так как ее вызов встречается в процедуре Rec1, т.е. перед ее полным описанием.
Program KosvRecurs;
Var
A: integer;
Procedure Rec2 (Var Y:integer); Forward;
{ - - - - - - - - - - - - - - - - - - - -}
Procedure Rec1 (Var X:integer);
Begin
X:= X-1;
if X>0
then
Rec2;
writeln (X)
End;
{ - - - - - - - - - - - - - - - - - - - -}
Procedure Rec2 (Var Y:integer);
Begin
Y:= Y div 2;
if Y>2
then
Rec1;
writeln (Y)
End;
{ - - - - - - - - - - - - - - - - - - - -}
Begin
A:= 15;
Rec1(A);
End.
Творческое задание. Придумайте и решите задачу на демонстрацию косвенной рекурсии в графическом режиме.
Решение задач. | ||
Для сдачи зачета приготовьте файлы и листинги с решенными задачами, а также будьте готовы ответить на теоретические вопросы, рассмотренные в этой теме.
Дата публикования: 2015-10-09; Прочитано: 767 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!