Рекурсивное вычисление чисел Фибоначчи

Можно рекурсивно определить числа Фибоначчи (Fibonacci numbers) при помощи уравнений:

Fib(0) = 0

Fib(1) = 1

Fib(N) = Fib(N - 1) + Fib(N - 2) для N > 1.

Третье уравнение рекурсивно дважды вызывает функцию Fib, один раз с входным значением N-1, а другой — со значением N-2. Это определяет необходимость 2 условий остановки рекурсии: Fib(0)=0 и Fib(1)=1. Если задать только одно из них, рекурсия может оказаться бесконечной. Например, если задать только Fib(0)=0, то значение Fib(2) могло бы вычисляться следующим образом:

Fib(2) = Fib(1) + Fib(0)

= [Fib(0) + Fib(-1)] + 0

= 0 + [Fib(-2) + Fib(-3)]

= [Fib(-3) + Fib(-4)] + [Fib(-4) + Fib(-5)]

И т.д.

Это определение чисел Фибоначчи легко преобразовать в рекурсивную функцию:

Public Function Fib(num As Integer) As Integer

If num <= 1 Then

Fib = num

Else

Fib = Fib(num – 1) + Fib(num - 2)

End If

End Function

=========86

Анализ времени выполнения программы

Анализ этого алгоритма достаточно сложен. Во‑первых, определим, сколько раз выполняется одно из условий остановки num <=1. Пусть G(N) — количество раз, которое алгоритм достигает условия остановки для входа N. Если N <= 1, то функция достигает условия остановки один раз и не требует рекурсии.

Если N > 1, то функция рекурсивно вычисляет Fib(N-1) и Fib(N-2), и завершает работу. При первом вызове функции, условие остановки не выполняется — оно достигается только в следующих, рекурсивных вызовах. Полное число выполнения условия остановки для входного значения N, складывается из числа раз, которое оно выполняется для значения N-1 и числа раз, которое оно выполнялось для значения N-2. Все это можно записать так:

G(0) = 1

G(1) = 1

G(N) = G(N - 1) + G(N - 2) для N > 1.

Это рекурсивное определение очень похоже на определение чисел Фибоначчи. В табл. 5.2 приведены некоторые значения функций G(N) и Fib(N). Легко увидеть, что G(N) = Fib(N+1).

Теперь рассмотрим, сколько раз алгоритм достигает рекурсивного шага. Если N<=1, функция не достигает этого шага. При N>1, функция достигает этого шага 1 раз и затем рекурсивно вычисляет Fib(n-1) и Fib(N-2). Пусть H(N) — число раз, которое алгоритм достигает рекурсивного шага для входа N. Тогда H(N)=1+H(N-1)+H(N-2). Уравнения, определяющие H(N):

H(0) = 0

H(1) = 0

H(N) = 1 + H(N - 1) + H(N - 2) для N > 1.

В табл. 5.3 показаны некоторые значения для функций Fib(N) и H(N). Можно увидеть, что H(N)=Fib(N+1)-1.

@Таблица 5.2. Значения чисел Фибоначчи и функции G(N)

======87

@Таблица 5.3. Значения чисел Фибоначчи и функции H(N)

Объединяя результаты для G(N) и H(N), получаем полное время выполнения для алгоритма:

Время выполнения = G(N) + H(N)

= Fib(N + 1) + Fib(N + 1) - 1

= 2 * Fib(N + 1) - 1

Поскольку Fib(N + 1) >= Fib(N) для всех значений N, то:

Время выполнения >= 2 * Fib(N) - 1

С точностью до порядка это составит O(Fib(N)). Интересно, что эта функция не только рекурсивная, но она также используется для оценки времени ее выполнения.

Чтобы помочь вам представить скорость роста функции Фибоначчи, можно показать, что Fib(M)>^M-2 где  — константа, примерно равная 1,6. Это означает, что время выполнения не меньше, чем значение экспоненциальной функции O(^M). Как и другие экспоненциальные функции, эта функция растет быстрее, чем полиномиальные функции, но медленнее, чем функция факториала.

Поскольку время выполнения растет очень быстро, этот алгоритм довольно медленно выполняется для больших входных значений. Фактически, настолько медленно, что на практике почти невозможно вычислить значения функции Fib(N) для N, которые намного больше 30. В табл. 5.4 показано время выполнения для этого алгоритма на компьютере с процессором Pentium с тактовой частотой 90 МГц при разных входных значениях.

Программа Fibo использует этот рекурсивный алгоритм для вычисления чисел Фибоначчи. Введите целое число и нажмите на кнопку Go для вычисления чисел Фибоначчи. Начните с небольших чисел, пока не оцените, насколько быстро ваш компьютер может выполнять эти вычисления.