К сожалению, рекурсивный алгоритм для подсчета чисел Фибоначчи содержит
не только хвостовую рекурсию. Алгоритм использует два рекурсивных обращения
для вычисления значения. Второй вызов следует после завершения первого. По-
скольку первый вызов находится не в самом конце функции, это не хвостовая ре-
курсия, поэтому ее нельзя удалить обычным способом.
Возможно, рекурсии нельзя избежать еще потому, что рекурсивный алгоритм
Фибоначчи ограничен скорее вычислением слишком большого количества проме-
жуточных значений, чем глубиной рекурсии. Удаление хвостовой рекурсии умень-
шает глубину рекурсии, но это не изменяет время выполнения алгоритма. Даже
без хвостовой рекурсии он все равно будет чрезвычайно медленным.
Проблема заключается в том, что алгоритм повторно вычисляет одни и те же
значения много раз. Значения Fib(l) и Fib(0) просчитываются Fib(N +1) раз при
вычислении Fib(N). Для определения Fib(29) алгоритм вычисляет значения Fib(0)
и Fib( 1) 832 040 раз.
Поскольку алгоритм повторно высчитывает одни и те же значения много раз,
необходимо отыскать способ, который бы позволил избежать повторных вычисле-
ний. Простой и конструктивный прием — сформировать таблицу расчетных значе-
ний. Когда потребуется промежуточное значение, можно взять его из таблицы, а не
вычислять заново.
В этом примере показано, как создать таблицу для хранения значений функ-
ции Фибоначчи Fib(N) для N 1477 происходит переполнение пе-
ременных типа Double, используемых функцией. В следующем коде представле-
на функция Фибоначчи с соответствующими изменениями:
Const
MAX_FIB=1476; // Самое большое значение, которое можно вычислить.
var
FiboValues : Array [O..MAX_FIB] of Double;
function Fibofn : Integer) : Double;
begin
// Вычисление значения, если его нет в таблице.
if (FiboValues[n] FiboValues[n] := Fibo(n-1)+Fibo(n-2);
Fibo := FiboValues[n];
end;
При запуске программа присваивает каждому элементу массива FiboValues
значение — единицу. Затем она устанавливает значение FiboValues [ 0 ] в нуль,
a FiboValues [ 1 ] — в единицу. Эти значения составляют основное условие ре-
курсии.
При выполнении функции массив проверяется на наличие необходимого зна-
чения. Если его там нет, функция рекурсивно вычисляет это значение и сохраняет
его для дальнейшего использования.
Программа Fibo2 использует этот метод для подсчета чисел Фибоначчи. Про-
грамма может быстро вычислять Fib(N) для N порядка 100 или 200. Но если вы
попробуете определить Fib(1476), то программа выполнит последовательность
рекурсивных вызовов глубиной 1476 уровней, в результате чего стек вашей систе-
мы, скорее всего, переполнится.
Альтернативный метод заполнения таблицы чисел Фибоначчи позволяет из-
бежать такой глубокой рекурсии. Когда программа инициализирует массив Fibo-
Values, она заранее вычисляет все числа Фибоначчи.
// Инициализация таблицы соответствия.
procedure TFiboForm.FormCreate(Sender : TObject);
var
i : Integer;
begin
FiboValues [0] := 0;
FiboValues [ 1 ] := 1;
for i := 2 to MAX_FIB do
FiboValues[i] := FiboValues[i-1]+FiboValues[i-2];
end;
// Поиск чисел Фибоначчи в таблице.
function Fibofn : Integer) : Double;
begin
Fibo : = FiboValues[n] ;
end;
При выполнении этого алгоритма определенное время занимает создание мас-
сива поиска. Как только массив готов, для обращения к значению массива требу-
ется всего один шаг. Ни процедура инициализации, ни функция Fib не использу-
ют рекурсию, поэтому ни одна из них не исчерпывает память стека. Программа
Fibo3 демонстрирует предложенный подход.
Стоит рассмотреть еще один метод вычисления чисел Фибоначчи. Первое ре-
курсивное определение функции Фибоначчи использует нисходящий способ.
Чтобы получить значение для Fib(N), алгоритм рекурсивно вычисляет Fib(N — 1)
и Fib(N — 2) и складывает их.
Процедура InitializeFibValues работает снизу вверх. Она начинает со
значений Fib(O) и Fib(l). Затем она использует меньшие значения для вычисле-
ния больших, пока таблица не заполнится.
Можно использовать эту стратегию, чтобы непосредственно вычислять значе-
ние функции Фибоначчи. Данный метод занимает больше времени, чем поиск
значений в массиве, но не требует дополнительной памяти для размещения масси-
ва. Это пример пространственно-временного компромисса. Чем больше памяти
используется для хранения таблицы, тем быстрее выполняется алгоритм.
function Fibo(n : Integer) : Double;
var
fib_i, fib_i_minus_1, fib_i_minus_2 : Double;
i : Integer;
begin
if (n Fibo := n
else
begin
fib_i := 0; // Предотвращает предупреждение компилятора.
fib_i_minus_2 := 0; //Начальное значение fib(0).
fib_i_minus_1 := 1; //Начальное значение fib(1).
for i := 2 to n do
begin
fib_i := fib_i_minus_l+fib_i_minus_2;
fib_i_itiinus_2 := f ib_i_minus_1 ;
fib_i_minus_1 := fib_i;
end;
Fibo := fib_i;
end;
end;
Для вычисления значения Fib(N) этой версии необходимо O(N) шагов. Это
больше, чем один шаг, который требовался в предыдущей версии, но гораздо быс-
трее, чем O(Fib(N)) в исходной версии алгоритма.
На компьютере, имеющем процессор Pentium с тактовой частотой 133 МГц,
первоначальный рекурсивный алгоритм вычислял бы Fib(40) = 1.02E + 8 более
155 с. Новый алгоритм не требует большого количества времени, чтобы опреде-
лить fib(1476) = 1,31Е + 308.