本講內(nèi)容
遞歸的定義
遞歸的特性
遞歸的寫法
遞歸的應(yīng)用
思考題：
推薦注冊返傭金
某app，用戶 A 推薦用戶 B 來注冊，用戶 B 又推薦了用戶 C 來注冊。我們可以說，用戶 C 的“最終推薦人”為用戶 A，用戶 B 的“最終推薦人”也為用戶 A，而用戶 A 沒有“最終推薦人”。
給定一個用戶 ID，如何查找這個用戶的“最終推薦人”？
遞歸的定義
遞歸是一種應(yīng)用非常廣泛的算法（或者編程技巧）。
先回憶下有哪些算法的實(shí)現(xiàn)用到了遞歸？
比如 DFS 深度優(yōu)先搜索、前中后序二叉樹遍歷等等。
函數(shù)或者方法自身調(diào)用自身則為遞歸。調(diào)用的過程成為遞，返回的過程成為歸
遞歸的特性
什么樣的問題可以用遞歸來解決呢？
- 一個問題的解可以分解為幾個子問題的解
- 這個問題與分解之后的子問題，除了數(shù)據(jù)規(guī)模不同，求解思路完全一樣
- 存在遞歸終止條件
遞歸的優(yōu)點(diǎn)是代碼的表達(dá)力很強(qiáng)，寫起來簡潔。
但是缺點(diǎn)也比較多：如空間復(fù)雜度高、有堆棧溢出風(fēng)險、存在重復(fù)計(jì)算、過多的函數(shù)調(diào)用會耗時較多等
遞歸的寫法
怎么寫遞歸算法？
關(guān)鍵：寫出遞推公式，找到終止條件
算法題：
假如這里有 n 個臺階，每次你可以跨 1 個臺階或者 2 個臺階，請問走這 n 個臺階有多少種走法？
如果有3個臺階， 走法有：
1，1，1
1，2
2，1
我們先來寫分析遞推公式
可以根據(jù)第一步的走法把所有走法分為兩類，第一類是第一步走了 1 個臺階，另一類是第一步走了 2 個臺階。所以 n 個臺階的走法就等于先走 1 階后，n-1 個臺階的走法 加上先走 2 階后，n-2 個臺階的走法。用公式表示就是：
f(n) = f(n-1)+f(n-2)
確定遞推公式后，接下來計(jì)算終止條件
當(dāng)有一個臺階時，我們不需要再繼續(xù)遞歸，就只有一種走法。所以 f(1)=1。
如果只有這一個終止條件，對于f (2) = f(1)+f(0)，無法求解，即要使得f(0)=1，但是f（0）實(shí)際是沒有意義的，所以我們把f (2) = 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ān)鍵就是找到如何將大問題分解為小問題的規(guī)律，并且基于此寫出遞推公式，然后再推敲終止條件，最后將遞推公式和終止條件翻譯成代碼。
編寫遞歸代碼的關(guān)鍵是，只要遇到遞歸，我們就把它抽象成一個遞推公式，不用想一層層的調(diào)用關(guān)系，不要試圖用人腦去分解遞歸的每個步驟。
遞歸常見問題和解決方法
堆棧溢出
在講棧的時候，我們講到函數(shù)調(diào)用會使用棧來保存臨時變量。每調(diào)用一個函數(shù)，都會將臨時變量封裝為棧幀壓入內(nèi)存棧，等函數(shù)執(zhí)行完成返回時，才出棧。系統(tǒng)棧或者虛擬機(jī)棧空間一般都不大。如果遞歸求解的數(shù)據(jù)規(guī)模很大，調(diào)用層次很深，一直壓入棧，就會有堆棧溢出的風(fēng)險。
解決方法：
限制遞歸調(diào)用的最大深度
但這種做法并不能完全解決問題，因?yàn)樽畲笤试S的遞歸深度跟當(dāng)前線程剩余的?？臻g大小有關(guān)，事先無法計(jì)算。如果實(shí)時計(jì)算，代碼過于復(fù)雜，就會影響代碼的可讀性。所以，如果最大深度比較小，比如 10、50，就可以用這種方法，否則這種方法并不是很實(shí)用。
代碼重復(fù)計(jì)算
如上圖，f(3),f(4)都存在重復(fù)計(jì)算的情況
解決方法：
緩存已經(jīng)計(jì)算過的數(shù)據(jù)
通過一個數(shù)據(jù)結(jié)構(gòu)（比如散列表）來保存已經(jīng)求解過的 f(k)。當(dāng)遞歸調(diào)用到 f(k) 時，先看下是否已經(jīng)求解過了。如果是，則直接從散列表中取值返回
遞歸代碼都是改為非遞歸代碼
因?yàn)檫f歸本身就是借助棧來實(shí)現(xiàn)的，只不過我們使用的棧是系統(tǒng)或者虛擬機(jī)本身提供的，我們沒有感知罷了。如果我們自己在內(nèi)存堆上實(shí)現(xiàn)棧，手動模擬入棧、出棧過程，這樣任何遞歸代碼都可以改寫成看上去不是遞歸代碼的樣子。
但這種做法實(shí)際是執(zhí)行了“手動”遞歸，本質(zhì)沒有改變，反而徒增了時間復(fù)雜度
