快速斐波那契遞推

Question

我想回想一個關於斐波那契遞歸的算法。以下：

public int fibonacci(int n) { 
    if(n == 0) 
    return 0; 
    else if(n == 1) 
    return 1; 
    else 
    return fibonacci(n - 1) + fibonacci(n - 2); 
} 

是不我要找的，因爲它是貪婪的。這將會成倍增長（只要看看Java recursive Fibonacci sequence - 初始參數越大，無用的呼叫就會越多）。

有可能是像「循環參數移位」，其中調用以前的斐波那契值將檢索值，而不是再次計算它。

Answer 1

也許像這樣的數組：

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); 
} 

這個功能是尾遞歸的。這意味着它可以非常有效地進行優化和執行。事實上，它被優化成一個簡單的循環..

Answer 2

說你想有那麼第n個謊數生成包含前述號碼

int a[n]; 
a[0] = 0; 
a[1] =1; 
a[i] = n[i-1]+n[n-2]; 

Answer 3

您可以使用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) 

Answer 4

這樣那樣的問題是線性遞歸類型，它們通過快速矩陣求冪運算得到最快解決方案。下面是描述這種方法的簡潔的blogpost。

Answer 5

I found interesting article about fibonacci problem

這裏的代碼片斷

# 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 

Answer 6

一個例子在使用遞歸和用於增加效率的延遲初始化緩存的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); 
}; 

Answer 7

duedl0r的算法轉換爲斯威夫特：

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 

Answer 8

一個好的算法快速斐波那契數計算爲（在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（）函數。

Answer 9

您需要記住計算的值以停止指數增長。

1. 只需使用數組來存儲值。
2. 如果您已經計算過它，請檢查該數組。
3. 如果發現它，請使用它或以其他方式計算並存儲它。

這是一個使用內存更快遞歸的工作示例。

Calculating fibonacci number