Нерекурсивное вычисление чисел Фибоначчи
К сожалению, нерекурсивный алгоритм вычисления чисел Фибоначчи не содержит только хвостовую рекурсию. Этот алгоритм использует два рекурсивных вызова для вычисления значения, и второй вызов следует после завершения первого. Поскольку первый вызов не находится в самом конце функции, то это не хвостовая рекурсия, и от ее нельзя избавиться, используя прием устранения хвостовой рекурсии.
Это может быть связано и с тем, что ограничение рекурсивного алгоритма вычисления чисел Фибоначчи связано с тем, что он вычисляет слишком много промежуточных значений, а не глубиной вложенности рекурсии. Устранение хвостовой рекурсии уменьшает глубину рекурсии, но оно не изменяет время выполнения алгоритма. Даже если бы устранение хвостовой рекурсии было бы применимо к алгоритму вычисления чисел Фибоначчи, этот алгоритм все равно остался бы чрезвычайно медленным.
Проблема этого алгоритма в том, что он многократно вычисляет одни и те же значения. Значения Fib(1)иFib(0)вычисляютсяFib(N + 1)раз, когда алгоритм вычисляетFib(N). Для вычисленияFib(29), алгоритм вычисляет одни и те же значенияFib(0)иFib(1)832.040 раз.
Поскольку алгоритм многократно вычисляет одни и те же значения, следует найти способ избежать повторения вычислений. Простой и конструктивный способ сделать это — построить таблицу вычисленных значений. Когда понадобится промежуточное значение, можно будет взять его из таблицы, вместо того, чтобы вычислять его заново.
В этом примере можно создать таблицу для хранения значений функции Фибоначчи Fib(N)дляN, не превосходящих 1477. ДляN >= 1477происходит переполнение переменных типаdouble, используемых в функции. Следующий код содержит измененную таким образом функцию, вычисляющую числа Фибоначчи.
Const MAX_FIB = 1476 ' Максимальное значение.
Dim FibValues(0 To MAX_FIB) As Double
Private Function Fib(N As Integer) As Double
' Вычислить значение, если оно не находится в таблице.
If FibValues(N) < 0 Then _
FibValues(M) = Fib(N - 1) + Fib(N - 2)
Fib = FibValues(N)
End Function
При запуске программы, она присваивает каждому элементу в массиве FibValuesзначение -1. Затем она присваиваетFibValues(0)значение 0, иFibValues(1)— значение 1. Это условия остановки рекурсии.
При выполнении функции, она проверяет, находится ли уже в массиве значение, которое ей требуется. Если его там нет, она, как и раньше, рекурсивно вычисляет это значение и сохраняет его в массиве для дальнейшего использования.
Программа Fibo2на диске с примерами использует этот метод для вычисления чисел Фибоначчи. Программа может быстро вычислитьFib(N)дляNдо 100 или 200. Но если вы попытаетесь вычислитьFib(1476), то программа выполнит последовательность рекурсивных вызовов глубиной 1476 уровней, которая вероятно переполнит стек вашей системы.
Тем не менее, по мере того, как программа вычисляет новые значения, она заполняет массив FibValues. Значения из массива позволяют функции вычислять все большие и большие значения без глубокой рекурсии. Например, если вычислить последовательноFib(100),Fib(200),Fib(300), и т.д. то, в конце концов, можно будет заполнить массив значенийFibValuesи вычислить максимальное возможно значениеFib(1476).
Процесс медленного заполнения массива FibValuesприводит к новому методу вычисления чисел Фибоначчи. Когда программа инициализирует массивFibValues, она может заранее вычислить все числа Фибоначчи.
Private Sub InitializeFibValues()
Dim i As Integer
FibValues(0) = 0 ' Инициализация условий остановки.
FibValues(1) = 1
For i = 2 To MAX_FIB
FibValues(i) = FibValues(i - 1) + FibValues(i - 2)
Next i
End Sub
Private Function Fib(N As Integer) As Duble
Fib - FibValues(N)
End Function
Определенное время в этом алгоритме занимает составление массива с табличными значениями. Но после того как массив создан, для получения элемента из массива требуется всего один шаг. Ни процедура инициализации, ни функция Fibне используют рекурсию, поэтому ни одна из них не приведет к исчерпанию стекового пространства. ПрограммаFibo3на диске с примерами демонстрирует этот подход.
Стоит упомянуть еще один метод вычисления чисел Фибоначчи. Первое рекурсивное определение функции Фибоначчи использует подход сверху вниз. Для получения значения Fib(N), алгоритм рекурсивно вычисляетFib(N - 1)иFib(N - 2)и затем складывает их.
Подпрограмма InitializeFibValues, с другой стороны, работает снизу вверх. Она начинает со значенийFib(0)иFib(1). Она затем использует меньшие значения для вычисления больших, до тех пор, пока таблица не заполнится.
Вы можете использовать тот же подход снизу вверх для прямого вычисления значений функции Фибоначчи каждый раз, когда вам потребуется значение. Этот метод требует больше времени, чем выборка значений из массива, но не требует дополнительной памяти для таблицы значений. Это пример пространственно‑временного компромисса. Использование большего объема памяти для хранения таблицы значений делает выполнение алгоритма более быстрым.
Private Function Fib(N As Integer) As Double
Dim Fib_i_minus_1 As Double
Dim Fib_i_minus_2 As Double
Dim fib_i As Double
Dim i As Integer
If N <= 1 Then
Fib = N
Else
Fib_i_minus_2 = 0 ' Вначале Fib(0)
Fib_i_minus_1 = 1 ' Вначале Fib(1)
For i = 2 To N
fib_i = Fib_i_minus_1 + Fib_i_minus_2
Fib_i_minus_2 = Fib_i_minus_1
Fib_i_minus_1 = fib_i
Next i
Fib = fib_i
End If
End Function