1. 如何理解遞歸并巍？
遞歸是一種應用非常廣泛的編程技巧，比如 DFS 深度優(yōu)先搜索刽射、前中后序二叉樹遍歷等都是使用遞歸剃执。
一個遞歸求解問題的分解過程，去的過程叫“遞”肾档，回來的過程叫“歸”∷状龋基本上，所有的遞歸問題都可以用遞推公式來表示低千。比如：
f(n) = f(n-1) + 1馏颂，其中 f(1) = 1。
遞歸的優(yōu)點和缺點：
- 優(yōu)點：遞歸代碼的表達力很強难审，寫起來非常簡潔亿絮。
- 缺點：空間復雜度高、有堆棧溢出的風險黔姜、存在重復計算蒂萎、過多的函數(shù)調用會耗時較多等問題。
2. 遞歸需要滿足的三個條件
一個問題的解可以分解為幾個子問題的解
這個問題與分解之后的子問題五慈，除了數(shù)據(jù)規(guī)模不同泻拦，求解思路完全一樣
存在遞歸終止條件
3. 如何編寫遞歸代碼？
寫遞歸代碼最關鍵的是寫出遞推公式争拐，找到終止條件陆错，剩下將遞推公式轉化為代碼就容易了。
假如這里有 n 個臺階音瓷，每次你可以跨 1 個臺階或者 2 個臺階夹抗，請問走這 n 個臺階有多少種走法？
仔細想下杏愤，n 個臺階的走法就等于先走 1 階后，n-1 個臺階的走法通殃，加上先走 2 階后厕宗，n-2 個臺階的走法。遞歸終止條件是 f(1)=1曲聂，f(2)=2佑惠。其實這就是著名的斐波那契數(shù)列。
f(n) = f(n-1) + f(n-2)旭咽，其中 f(1) = 1赌厅，f(2) = 2。
最終的遞歸代碼：
int f(int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
return f(n-1) + f(n-2);
}
總結一下请垛，寫遞歸代碼的關鍵就是找到如何將大問題分解為小問題的規(guī)律洽议，并且基于此寫出遞推公式，然后再推敲終止條件混稽，最后將遞推公式和終止條件翻譯成代碼审胚。
只要遇到遞歸，就把它抽象成一個遞推公式膳叨，不用想一層層的調用關系菲嘴，不要試圖用人腦去分解遞歸的每個步驟汰翠。
4. 警惕堆棧溢出和重復計算
函數(shù)調用會使用棧來保存臨時變量昭雌。每調用一個函數(shù)，都會將臨時變量封裝為棧幀壓入內存棧佛纫，等函數(shù)執(zhí)行完成返回時总放，才出棧。如果遞歸求解的數(shù)據(jù)規(guī)模很大攒盈，調用層次很深哎榴，一直壓入棧，就會有堆棧溢出的風險迎变。
可以通過限制遞歸調用的最大深度的方式飘言，來解決堆棧溢出。
比如上面的遞歸谆吴，想要計算 f(5)苛预，需要先計算 f(4) 和 f(3)，而計算 f(4) 還需要計算 f(3)腻菇，因此昔馋，f(3) 就被計算了很多次，這就是重復計算問題丘薛。
可以通過一個數(shù)據(jù)結構（比如散列表）來保存已經求解過的值垄提，解決重復計算周拐。
5. 將遞歸代碼改為非遞歸
籠統(tǒng)地講凰兑，如果我們自己在內存堆上實現(xiàn)棧审丘，手動模擬入棧滩报、出棧過程，這樣任何遞歸代碼都可以改寫成看上去不是遞歸代碼的樣子脓钾。
將斐波那契數(shù)列改為非遞歸方式實現(xiàn)：
int f(int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
int ret = 0;
int pre = 2;
int prepre = 1;
for (int i = 3; i < n; i++) {
ret = pre + prepre;
prepre = pre;
pre = ret;
}
return ret;
}
練習題
- 編程實現(xiàn)求階乘n!
- 編程實現(xiàn)一組數(shù)據(jù)集合的全排列
