Пример обработки рекуррентной последовательности

Begin

clrscr;

write('Какое по счету число Фиббоначчи вывести? ');

readln(n);

writeln('Итеративно:',fibit(n):5);

writeln('Рекурсивно:');

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);

Итерация требует меньше места в памяти и машинного времени, чем рекурсия, которой необходимы затраты на управление стеком.

Итак, если для некоторой задачи возможны два решения, предпочтение следует отдать итерации. Правда, для многих задач рекурсивная формулировка совершенно прозрачна, в то время как построение итерации оказывается весьма сложным делом.

Рекурсивный метод решения задач является чуть ли не базовым методом решения алгоритмических задач. Рекурсия, дополненная идеями динамического программирования, жадными алгоритмами и идеей отсечения, превращается в тяжёлую артиллерию программистов. Но не следует забывать, что краткость записи рекурсивных функций не всегда означает высокую скорость их вычисления. И есть ряд задач, в которых рекурсия просто вредна (такова, например, задача вычисления кратчайшего пути в графе).

Техника работы с рекуррентными соотношениями полезна также при составлении программ обработки последовательностей, когда эффективнее не вычислять каждый член по общей формуле, а получать очередной элемент, зная значение предыдущего.

Рассмотрим задачу суммирования ряда:

Конечно, можно для каждого слагаемого вычислять , но тогда время суммирования сильно возрастет.

Вычисление можно ускорить, если воспользоваться соотношением: . Слагаемые ряда можно определить при помощи рекуррентной последовательности первого порядка:

, .

Сумма накапливается параллельно с вычислением элемента рекуррентной последовательности, удовлетворяющего заданному условию.

program Sum;
var
n, k: integer;
a, s: real;
begin
writeln ('Введите целое число n');
readln (n);
a:=1;
s:=a;
for k:=1 to n do
begin
a:=a/2;
s:=s+a;
end;
writeln ('Сумма равна ', s:5:3);
end.

Дата добавления: 2014-01-03