遞歸算法與動態規劃算法是計算機程序設計、數據結構中常見算法。有些書籍教材中對遞歸算法與動態規劃算法比較時，總是指出動態規劃算法優于遞歸算法，在問題較為復雜時不建議使用遞歸算法。本文主要以在實際問題解決過程中對遞歸算法與動態規劃算法進行比較，判斷其時間復雜度。
計算機程序算法分析
1、問題
假設某人爬樓梯，一次只能攀爬1臺階或者2臺階，某樓梯共有N階，請計算該人爬上N階樓梯一共有多少種方法？
2、遞歸算法
該問題與斐波那契數列十分類似，是一道地地道道的遞歸題目，因此可以直接使用遞歸算法實現問題求解。編寫函數如下：
爬樓梯問題遞歸算法
3、動態規劃算法
解決爬樓梯問題采用動態規劃算法則可以從1層開始，計算到N層每層能夠到達的方法，設計a，b兩變量時刻表示到達每一層K前的兩層，a是到達k-2層的方法，b是到達k-1層的方法。則可編寫函數實現問題求解。函數定義如下：
爬樓梯問題動態規劃算法求解
以上給出爬樓梯問題動態規劃與遞歸算法求解函數，其中f(n)是用遞歸實現， v(n)是用動態規劃實現。以臺階數為10，調用函數執行，可獲取以下結果。
計算結果
如上圖結果所示，當樓梯數量為10時，分別計算方法總數為89.為研究兩種算法時間復雜度，我們在函數外部分別定義全局函數 count1和count2,為計數器，在兩個函數內部執行++運算。如圖：
設置計數變量之后，繼續調用兩函數計算爬樓方法，當N=20時可以獲取以下結果：
函數調用執行次數
由此可見，使用動態規劃與遞歸算法執行問題求解過程N=20時，兩函數調用次數差距較大，其中動態規劃執行18次，遞歸算法執行了13529次。有興趣讀者可以自己嘗試一下當N=50時可能遞歸算法將會導致瀏覽器卡死。因此在解決這個問題方面動態規劃時間復雜度較低，僅為O(n),遞歸算法時間復雜度為O(2^n).
