一、什麼是遞歸？
1、初中數學題 -- 根據數字找規律:
1,1,2,3,5,8,( ),21... 求括號中的數字？
通過從左到右觀察，我們可以看出，從第 2 個數開始，後一個數等於前兩個數之和。
2 = 1 + 1；3 = 2 + 1；5 = 3 + 2；8 = 5 + 3；
可以得出括號內的數為 5 + 8 = 13。
這是一個斐波那契數列，也是一個典型的遞歸數列。
我們可以得出一個表達式：
F (1) = 1，
F (2) = 1,
F (n) = F (n-1) + F (n-2)（n>=3，n∈N*）
2、如何理解 “遞歸”？
① 兩個必要條件
● 遞歸條件
“遞歸條件”指的是自己調用自己，比如 F (n) = F (n-1) + F (n-2)
● 基線條件
在遞歸終止條件，不再調用自己，從而比避免進入死循環
② 遞歸代碼
Python代碼
輸出結果
③ 總結
寫遞歸代碼的關鍵就是找到如何將大問題分解為小問題，並且基於此寫出遞推公式，然後再推敲終止條件，最後將遞推公式和終止條件翻譯成代碼。
二、遞歸的優缺點
1、優點
● 代碼的表達力強，書寫簡潔。
2、缺點
● 遞歸會利用棧保存臨時變量，如果遞歸過深，會造成棧溢出。
解決方案是控制遞歸的深度。
● 存在重複計算、過多的函數調用會耗時較多等問題
斐波那契數列遞歸求 fn(6)
圖
從上圖中可看出，會進行重複計算
三、遞歸函數轉換為非遞歸函數
四、建議
遞歸代碼雖然簡潔高效，但是，遞歸代碼也有很多弊端。比如，堆棧溢出、重複計算、函數調用耗時多、空間複雜度高等，所以，在編寫遞歸代碼的時候，一定要控制好這些副作用。
>>>
分享到:
閱讀更多 Python大星 的文章
