Рекурсия

Содержание Рекурсия . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Пример 1 . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Пример 2 . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Пример 3 . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Пример 4 . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Пример 5 . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Рекурсия. Рекурсией называется ситуация, когда процедура или функция сама себя вызывает.

Вот типичная конструкция такого рода: 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.