斐波那契數列的遞歸演算法

⑴ ［數據結構與演算法分析］斐波那契數列遞歸演算法時間復雜度為多少

longfab(longn)
{
if(n<2)return1;
returnfab(n-1)+fab(n-2);
}

簡單推斷一下，當n>2時，遞歸調用的次數call_fab(n) = 2*fab(n) - 1，再簡單證明一下。

用call_fab(n)代表遞歸調用的次數

n = 3時，調用fab(3)，會遞歸調用fab(1)和fab(2)，而fab(1)和fab(2)只需要調用一次，加上本身一次，一共調用3次，而fab(3) = 2，3 = 2 * 2 - 1，滿足推斷

n = 4時，fab(4) = fab(3) + fab(2)，所以call_fab(4) = 1 + call_fab(3) + call_fab(2) = 5

fab(4) = 3，滿足5 = 3 * 2 - 1

同理n=5也可以簡單計算得出，這樣我有連續3個結果，作為歸納法證明的基礎

假設n = k（k >= 5）成立，即

fab(k) = fab(k-2) + fab(k - 1)，有call_fab(k) = 2fab(k) - 1

那麼當n=k+1時，fab(k+1) = fab(k - 1) + fab(k)，

call_fab(k+1) = 1 + call_fab(k - 1) + call_fab(k) = 1 + 2fab(k-1) - 1 + 2fab(k) - 1

= 2(fab(k-1) + fab(k)) - 1 = 2fab(k+1) - 1，歸納法得證。

所以，對於大於2的整數n，其斐波那契數列遞歸演算法的調用次數為2*n的斐波那契數列值 - 1，故答案是D，時間復雜度和該數列是一致的。