Рекурсия

| Категория реферата: Рефераты по кибернетике
| Теги реферата: реферат федерация, алгебра
| Добавил(а) на сайт: Bychkov.

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 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(‘’:60); read(c,c); end; end; end.