Я пытаюсь вспомнить алгоритм рекурсии Фибоначчи. Следующее:
public int fibonacci(int n) {
if(n == 0)
return 0;
else if(n == 1)
return 1;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}
не, что я ищу, потому что он жадный. Это будет экспоненциально расти (просто посмотрите рекурсивную последовательность Fibonacci Java - чем больше начальный аргумент, тем более бесполезные вызовы будут сделаны).
Возможно, что-то похожее на "циклический сдвиг аргумента", где вызов предыдущего значения Фибоначчи будет извлекать значение, а не вычислять его снова.
может быть так:
int fib(int term, int val = 1, int prev = 0)
{
if(term == 0) return prev;
if(term == 1) return val;
return fib(term - 1, val+prev, val);
}
эта функция является хвостовой рекурсивной. это означает, что он может быть оптимизирован и выполнен очень эффективно. Фактически, он оптимизируется в простой цикл.
Такие проблемы представляют собой линейные рекуррентные типы, и они решаются быстрее с помощью быстрого экспоненциального матричного преобразования. Здесь blogpost, который кратко описывает этот подход.
Вы можете сделать довольно быструю версию рекурсивного Фибоначчи, используя memoization (это означает: сохранение предыдущих результатов, чтобы избежать их повторного вычисления). например, здесь доказательство концепции в Python, где словарь используется для сохранения предыдущих результатов:
results = { 0:0, 1:1 }
def memofib(n):
if n not in results:
results[n] = memofib(n-1) + memofib(n-2)
return results[n]
Он быстро возвращается для входных значений, которые обычно блокируют "нормальную" рекурсивную версию. Просто имейте в виду, что тип данных int не будет достаточным для проведения больших результатов и рекомендуется использовать произвольные целые числа точности.
Другой вариант - переписать эту итеративную версию...
def iterfib(n):
a, b = 0, 1
for i in xrange(n):
a, b = b, a + b
return a
... как хвосто-рекурсивная функция, называемая loop в моем коде:
def tailfib(n):
return loop(n, 0, 1)
def loop(i, a, b):
if i == 0:
return a
return loop(i-1, b, a+b)
Я нашел интересную статью о проблеме с Фибоначчи
здесь фрагмент кода
# Returns F(n)
def fibonacci(n):
if n < 0:
raise ValueError("Negative arguments not implemented")
return _fib(n)[0]
# Returns a tuple (F(n), F(n+1))
def _fib(n):
if n == 0:
return (0, 1)
else:
a, b = _fib(n // 2)
c = a * (2 * b - a)
d = b * b + a * a
if n % 2 == 0:
return (c, d)
else:
return (d, c + d)
# added iterative version base on C# example
def iterFib(n):
a = 0
b = 1
i=31
while i>=0:
d = a * (b * 2 - a)
e = a * a + b * b
a = d
b = e
if ((n >> i) & 1) != 0:
c = a + b;
a = b
b = c
i=i-1
return a
Предположим, что вы хотите, чтобы число n-го фибра строилось с массивом, содержащим предыдущие числа
int a[n];
a[0] = 0;
a[1] =1;
a[i] = n[i-1]+n[n-2];
Пример в JavaScript, который использует рекурсию и лениво инициализированный кеш для повышения эффективности:
var cache = {};
function fibonacciOf (n) {
if(n === 0) return 0;
if(n === 1) return 1;
var previous = cache[n-1] || fibonacciOf(n-1);
cache[n-1] = previous;
return previous + fibonacciOf(n-2);
};
алгоритм duedl0r, переведенный в Swift:
func fib(n: Int, previous: (Int, Int) = (0,1)) -> Int {
guard n > 0 else { return 0 }
if n == 1 { return previous.1 }
return fib(n - 1, previous: (previous.1, previous.0 + previous.1))
}
приведен пример:
fib(4)
= fib(4, (0,1) )
= fib(3, (1,1) )
= fib(2, (1,2) )
= fib(1, (2,3) )
= 3
Хорошим алгоритмом для быстрого вычисления фибоначчи является (в python):
def fib2(n):
# return (fib(n), fib(n-1))
if n == 0: return (0, 1)
if n == -1: return (1, -1)
k, r = divmod(n, 2) # n=2k+r
u_k, u_km1 = fib2(k)
u_k_s, u_km1_s = u_k**2, u_km1**2 # Can be improved by parallel calls
u_2kp1 = 4 * u_k_s - u_km1_s + (-2 if k%2 else 2)
u_2km1 = u_k_s + u_km1_s
u_2k = u_2kp1 - u_2km1
return (u_2kp1, u_2k) if r else (u_2k, u_2km1)
def fib(n):
k, r = divmod(n, 2) # n=2k+r
u_k, u_km1 = fib2(k)
return (2*u_k+u_km1)*(2*u_k-u_km1)+(-2 if k%2 else 2) if r else u_k*(u_k+2*u_km1)
Если вам нужно очень быстрое вычисление, ссылки на libgmp и использовать функции mpz_fib_ui() или mpz_fib2_ui().
Чтобы остановить экспоненциальный рост, вам нужно запомнить вычисленное значение.
Вот рабочий пример для быстрой рекурсии с использованием памяти.