Рекурсия и рекуррентность.

С понятием рекурсия тесно связано понятие рекуррентное соотношение (оба слова имеют общий корень от латинского recurro – возвращаться, бежать назад). Запишем в общем виде рекуррентное соотношение порядка к:

f(n) = G (n, f (n - 1),f (n - 2), … f (n - k)), (2)

где G – некоторая функция к + 1 аргумента.

Если известны начальные значения f(1), f(2), …f(k), то выражение (2) позволяет однозначно определить f(n). Выбрав другие начальные условия, получим тем же способом другую функцию от n, удовлетворяющую (2). Каждая такая функция является решением данного рекуррентного соотношения.

Рассмотрим рекуррентную числовую последовательность Фибоначчи, играющую важную роль в математике:

f(0) = 0; f (1) = 1

f (n) = f (n-1) + f (n-2), (3)

Запишем несколько первых значений последовательности чисел Фибоначчи:

f(2)=1;

f(3)=2;

f(4)=3;

f(5)=5;

f(6)=8;

f(7)=13;…..

Простейшее рекуррентное соотношение второго порядка (3), в котором каждое следующее значение вычисляется по двум предыдущим, может быть естественным образом реализовано в виде рекурсивной функции:

function Fib(n:integer):integer;

begin

if (n = Ø) then Fib:= Ø;

if (n = 1) then Fib:= 1

else Fib:= Fib(n – 2) + Fib(n-1)

end;

Приведем не рекурсивный вариант решения данной задачи:

function Fib(n:integer):integer;

var i,j,k,m: integer;

begin

m:=Ø; k:=1;

for i:=2 to n do begin

j:=k; k:=k+m; m:=j;

end;

Fib:=k

end;

Сравнение этих подпрограмм показывает, что рекурсивный вариант организован не лучшим образом, он менее экономичен по числу обращений к функции. Это и понятно, вычисление слагаемого f(n) требует ссылки на f(n-1) и f(n-2). А вычисление слагаемого f(n-1), в свою очередь, на f(n-2) и f(n-3), т.е. происходит два независимых вычисления f(n-2). Это можно проиллюстрировать в виде следующего дерева графа для n = 4:

4

3 2

2 1 1 0

1 0

Из девяти вызовов функции f(n) - четыре сделаны повторно. Это неэффективно.

Приведем аналитическое решение рекуррентного соотношения (3):

(4)

Нетрудно показать, что вычисление по рекурсивному алгоритму требует обращений к функции, в отличие от N₁ = (n – 2) обращений во второй программе, использующей цикл. Зависимость N₁ от n - линейная, а N₂ от n - показательная с основанием , т.е. .

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

Дата добавления: 2015-07-26