1.普通遞歸

這里觀察f[4]的遞歸樹代替f[10]的遞歸樹（后者比較大，畫不下）。

使用遞歸求解的時候復雜度為$T(n)=T(n?1)+T(n?2)$，觀察遞歸樹，發現降速最快的是最右邊每次減2，因此$\frac{n}{2}$層以上的部分肯定是滿二叉樹，因此時間復雜度肯定是$\Omega (2^{\frac{n}{2}})$的，再加上其他節點，因此我們可以大概認為時間復雜度為$O(2^n)$，空間復雜度為樹的深度為$O(n)$

實現代碼

ll Fibo(ll n)
{if(n<2) return n;return Fibo(n-1)+Fibo(n-2);
}

2.尾遞歸

通過改變函數的形式，能夠讓結果在最底層調用時直接返回。這樣我們就可以在每一層函數尾調用自身來實現尾遞歸。因為編譯器發現函數最后是尾調用（直接返回另一個函數）的時候將不會保存原函數的棧幀（因為已經執行結束），而是直接帶著上一個棧幀的結果直接在原地進入下一棧幀。這樣就沒有遞歸調用時空間的額外消耗。

對于本問題，使用尾遞歸的話時間復雜度為$O(n)$，空間復雜度為$O(1)$

ll Fibo2(ll n,ll x,ll y)//y保存當前項，調用時x=0，y=1，表示當前項為1
{if(1 == n) return y;return Fibo2(n-1, y, x+y);
}

3. 記憶化搜索

為了避免對已經計算過的值再次計算，我們用一個數組保存已經計算過的值。這樣的時間復雜度將變為$O(n)$，空間復雜度也為$O(n)$

ll Work3(ll n, ll* ans)
{if(n<2) return ans[n]=n;if(ans[n]) return ans[n];return ans[n]=Work3(n-1, ans)+Work3(n-2, ans);
}ll Fibo3(ll n)
{ll *ans = new ll[n+5]();ll ret = Work3(n, ans);delete[] ans;return ret;
}

4. 遞推

斐波那契有遞推公式：$Fibo[n]=Fibo[n?1]+Fibo[n?2]$，因此可以用遞推解決。如果記憶所有項的話，空間復雜度為$O(n)$，如果不記憶的話空間復雜度為$O(1)$。時間復雜度為$O(n)$

ll Fibo4(ll n)
{ll *ans = new ll[n+5];ans[1]=1;for(ll i=2;i<=n;++i) ans[i]=ans[i-1]+ans[i-2];ll ret=ans[n];delete[] ans;return ret;
}

性能測試

#include <iostream>
#include <algorithm>
#include <ctime>using namespace std;typedef long long ll;
typedef ll (*FP)(ll);ll Fibo1(ll n)
{if(n<2) return n;return Fibo1(n-1)+Fibo1(n-2);
}ll Work2(ll n,ll x=0,ll y=1)//y保存當前項，調用時x=0，y=1，表示當前項為1
{if(1 == n) return y;return Work2(n-1, y, x+y);
}ll Fibo2(ll n)
{return Work2(n);
}ll Work3(ll n, ll* ans)
{if(n<2) return ans[n]=n;if(ans[n]) return ans[n];return ans[n]=Work3(n-1, ans)+Work3(n-2, ans);
}ll Fibo3(ll n)
{ll *ans = new ll[n+5]();ll ret = Work3(n, ans);delete[] ans;return ret;
}ll Fibo4(ll n)
{ll *ans = new ll[n+5];ans[1]=1;for(ll i=2;i<=n;++i) ans[i]=ans[i-1]+ans[i-2];ll ret=ans[n];delete[] ans;return ret;
}void Test(ll n,FP fp[])
{clock_t S,E;for(int i=0;i<4;++i){int T=10;double sum=0;for(int j=0;j<T;++j){S=clock();fp[i](n);E=clock();sum+=(double)(E-S)/CLOCKS_PER_SEC;}cout<<"方法"<<i+1<<"平均用時"<<sum/T<<"s"<<endl;}
}int main()
{FP fp[4]={Fibo1,Fibo2,Fibo3,Fibo4};ll n;cout<<"請輸入需要查詢斐波那契數列第幾項："; cin>>n;Test(n,fp);return 0;
}

運行結果

性能分析

可以看到后面幾種方法的復雜度相差不多，但是同樣是遞歸處理，尾遞歸比普通遞歸的復雜度明顯優秀很多，所以如果可以的話應該盡量將遞歸變成尾遞歸的方式進行處理。