Рекурсия
Рекурсия.
Рекурсией называется ситуация, когда процедура или функция сама себя вызывает. Вот типичная конструкция такого рода:
procedure
proc(i:integer);
begin
anweisungen1;
if bedingung then proc(i+1);
anweisungen2;
end;
Вызов
proc(1) означает, что proc
вызывает себя раз за разом с помощью proc(2), proc(3),..
до тех пор, пока условие bedingung
не
отменит новый вызов. При каждом вызове
выполняется оператор anweisungen
1, после чего порядок выполнения операторов
прерывается новым вызовом proc(i+1).
Чтобы для каждого вызова был отработан и
оператор anweisungen2,
все локальные переменные процедуры
сохраняются в стеке. Стеком является
структура магазинного типа LIFO (Last In First
Out), т.е.
если, например, при proc(10) условие более не
выполняется, anweisungen2
выполняется со значениями, обрабатываемыми
в обратном порядке для proc(9),…,proc(1).
Локальные параметры помещаются в стек один
за другим и выбираются из стека в обратной
последовательности (латинское recurrere
означает
«возвращение назад»).
В Паскале можно пользоваться именами
лишь тогда, когда в тексте программы этому
предшествует их описание. Рекурсия
является единственным исключением из этого
правила. Имя proc
можно использовать сразу же, не закончив
его описания.
Пример1 представляет собой бесконечную
рекурсию, с помощью которой можно
установить, насколько велик стек. При этом
помните, что при использовании директивы (*$S+*)
при переполнении стека получим сообщение
об ошибке; а при использовании директивы (*$S-*) –
нет, а значит, мы скорее всего столкнемся с
зависанием системы. Установкой по
умолчанию является (*$S+*).
Программа будет прервана с выдачей
сообщения об ошибке «Error
202: stack overflow
error
(“Ошибка 202: переполнение стека»).
Пример1:
Program stack_test;
{программа проверки стека}
procedure
proc(i:integer);
begin
if i mod 1024 = 0
then writeln(i:6);
proc(i+1);
end;
begin
proc(1);
end.
Стек
связан с другой структурой памяти – с
динамической областью. С помощью директивы
(*$М*) можно управлять размером стека.
Рекурсия не должна восприниматься как
некий программистский трюк. Это скорее
некий принцип, метод. Если в программе нужно
выполнить что-то повторно, можно
действовать двумя способами:
- с
помощью последовательного присоединения (или
итерации в форме цикла);
- с
помощью вложения одной операции в другую (а
именно, рекурсий).
В
следующем примере2 один раз счет от 1 до n
ведется с помощью цикла, а второй – с
помощью рекурсии. При этом хорошо видно, как
заполняется, а затем освобождается стек. В
процедуре rekursion
операция
writeln(i:30)
выполняется перед рекурсивным вызовом,
после чего writeln(i:3)
освобождает стек. Поскольку рекурсия
выполняется от n
до 1, вывод по команде writeln(i:30)
выполняется в обратной последовательности n,n-1,…,1,
а вывод по команде writeln(i:3) –
в прямой последовательности 1,2,…,n
(согласно
принципу LIFO –
последним пришел, первым обслужен).
Пример2:
Показывает принципиальное
различие между итерацией и рекурсией:
итерации необходим цикл и локальная
переменная k
как переменная цикла. Рекурсии ничего этого
не требуется!
program
iterativ_zu_rekursion;
var n:integer;
procedure rekursion (i:integer);
begin
writeln(i:30);
if i < 1 then rekursion(i-1);
writeln(i:3);
end; (* Рекурсия *)
procedure schleife(i:integer);
var k:integer;
bagin
k :=1;
while k <= i do begin
write(k:3);
k :=k+1;
end;
end; (* Цикл
*)
begin
write(‘Введите
n:’); readln(n);
writeln(‘Пока:’);
scheife(n);
writeln;
writeln(‘Рекурсия’);
rekursion(n);
end.
Пример3:
Рекурсивная
процедура convert переводит десятичное число z
в
восьмеричную систему путем деления его на 8
и выдачи остатка в обратной
последовательности.
Program dezimal_oktal_konvertierung;
{преобразование
из десятичной системы в восьмеричную}
var z:integer;
procedure convert(z:integer);
begin
if z > 1 then convert(z div 8);
(* Это
рекурсивный вызов *)
write(z mod 8:1);
end;
begin
writeln(‘Введите
некоторое положительное число:’);
readln(z);
writeln(‘Десятичное
число:’,z:6);
write(‘Восьмеричное
число: ’);
convert(z);
end.
Один из наиболее ярких
примеров применения рекурсии дают числа
Фибоначчи. Они определяются следующим
образом:
x[1]=x[2]=1
x[n]=x[n-1]+x[n-2]
при n > 2
Каждый
элемент ряда Фибоначчи является суммой
двух предшествующих элементов, т.е.
1 1
2 3 5 8
13 21
34 55 …
Следующий
пример позволяет вычислить n-ный
элемент ряда Фибоначчи как итеративно (то
есть в цикле, начиная с х[1] до х[n]),
так и рекурсивно (n-ный
элемент ряда является суммой двух
предшествующих элементов). Причем
рекурсивная функция вызывает себя дважды.
Пример4:
С
использованием рекурсии вычисляются числа
Фибоначчи, причем глубина рекурсии
индицируется. Перед каждым рекурсивным
вызовом выводится выводиться
ASCII-символ
с номером 8 (Backspace),
а после вызова вновь стирается. Тем самым
можно наблюдать за работой программы,
поскольку программа за счет delay(300)
приостанавливается на 0.3 с.
program fibonacci(input, output);
uses crt;
var n,result:integer;
function fibit(n:integer):integer;
var a,b,c,i:integer;
begin
a := 1; b := 1;
if (n=1) or (n=2)
then fibit :=1
else begin
for i= 3
to n do
begin c
:=a+b; a := b; b :=c; end;
fibit :=c;
end;
end;
begin
clrscr;
write(‘n = ‘);
readln(n);
writeln(‘Итеративно:’,fibit(n):5);
writeln(‘рекурсивно:’);
write(‘
….!….#….!….#….’);
writeln(‘!….#….!….#….!….#’);
write (‘Глубина рекурсии:’);
result := fibrek(n);
writeln;
write(result);
end.
Этот пример демонстрирует прежде всего
различия между итерацией и рекурсией.
Итерации необходим цикл и вспомогательные
величины; итерация сравнительно ненаглядна
(см. fibit
в
приведенном выше примере). Рекурсия
обходится без вспомогательных величин и
обычно проще для понимания, что
демонстрирует следующая запись:
if
(n=1) or (n=2) then fibrek := 1
else fibrek := fibrek(n-1)+fibrek(n-2);
Итерация
требует меньше места в памяти и машинного
времени, чем рекурсия, которой необходимы
затраты на управление стеком. Итак, если для
некоторой задачи возможны два решения,
предпочтение следует отдать итерации.
Правда, для многих задач рекурсивная
формулировка совершенно прозрачна, в то
время как построение итерации оказывается
весьма сложным делом.
Если процедура или функция вызывает
себя сама, это называют прямой рекурсией. Но
может встретиться ситуация, когда
процедура А вызывает процедуру В,
вызывающую С, а процедура С вновь
возвращается к А. В этом случаи мы имеем
дело дело с косвенной рекурсией, что
демонстрирует приведенный ниже пример. С
таким типом рекурсии мы сталкиваемся там,
где использована директива forward.
Пример 5:
Следующая программа выдает простые
числа от 1 до n, для чего используются функции next
и prim,
которые вызываются перекрестно, то есть
рекурсивно. Одновременно это является
примером применения директивы forward.
program
primzahlen_rekursiv_berechnen;
{программа рекурсивного
вычисления простых чисел}
var
n,i : integer;
c : char;
function next(i:integer):integer;forward;
{Это
прямая ссылка вперед на функцию next,
которая
будет определена позже}
function
prim(j:integer):boolean;
{prim
имеет
значение true,
если j простое число,
и false
в
противном случае}
var
k:integer;
begin
k :=2;
while (k*k <= j) and (j mod k < > 0) do
k :=next(k);
{k
пробегает последовательность простых
чисел, начиная с 2,
вплоть
до корня из j, при этом проверяется,
делится ли j на
одно
из таких простых чисел. При этом
используется
следующая
функция next}
if
j mod k = 0 then prim := false
else prim := true;
end {prim};
function next;
{Параметры
уже стоят в ссылке вперед,
next вычисляет, каково следующее за j
простое число}
var
i:integer;
begin
1 :=i+1;
while not(prim(1)) do 1 :=1+1;
{Итак, next
вызывает в свою очередь prim}
next
:=1;
end {next};
begin
(******* Исполняемая часть программы *******)
write(‘Введите
положительное число n,’);
writeln(‘Должны
быть определены все’);
writeln(‘предшествующие
ему простые числа’);
readln(n);
for i :=2 to n do
begin
if prim(i) then writeln(i:14)
else writeln(i:4);
if i mod 23 = 0 then begin
write(‘<RET>’:60); read(c,c);
end;
end;
end.
