10.遞歸：如何用三行代碼找到“最終推薦人”？
markdown檔案已上傳至github
推薦注冊傭金這個功能大家應該都不陌生吧。使用者A推薦使用者B來注冊，B推薦C注冊。這裡，使用者B和使用者C的最終“推薦人”都為使用者A，使用者A沒有最終“最終推薦人”。
可以用資料庫來記錄這種推薦關系。在資料庫表中，我們可以記錄兩行資料，actor_id表示使用者ID,referrer_id表示推薦人ID。
**給定一個使用者ID，如何查找這個使用者的“最終推薦人”？
解決這個問題，可以用遞歸。
1.如何了解遞歸？
周末帶着女朋友去看電影，女朋友問你咱們現在坐在第幾排？電影院太黑，看不清，沒法數。怎麼辦？
遞歸的思想：你可以問前面的人他在第幾排，隻要在它的數字上加一就知道自己在哪一排了。前一排的人也不知道自己在第幾排，他也問他前一排的人。就這樣一排一排往前問，直到問到第一排的人，說他在第一排，然後在這樣一排一排再把數字傳回來。于是你就知道自己在第幾排了。
這就是一個遞歸分解問題求解的過程，去的過程叫做“遞”，回的過程叫做“歸’’。
所有的遞歸問題都可以用遞歸公式來表示。
f ( n ) = f ( n − 1 ) + 1 其 中 ， f ( 1 ) = 1 f(n) = f(n-1) +1 \space 其中，f(1)=1 f(n)=f(n−1)+1 其中，f(1)=1
f ( n ) f(n) f(n)表示你想知道自己在第幾排， f ( n − 1 ) f(n-1) f(n−1)表示前一排所在排數， f ( 1 ) = 1 f(1)=1 f(1)=1表示第一排的人知道自己在第一排。
有了遞歸公式就容易寫出代碼了：
int f(int n) {
if (n == 1) return 1;
return f(n-1) + 1;
}
2. 遞歸需要滿足的條件。
隻要滿足下列三個條件，就可以用遞歸來解決。
1.一個問題的解可以分解為幾個子問題的解。
子問題：資料規模更小的問題。
2.這個問題與分解之後的子問題，除了資料規模不同，求解思路完全一樣。
3.存在遞歸終止條件。
把問題分解為子問題，子問題再分解為子問題，終止條件就是分解到某個子問題時，該子問題的解已經知道。
3.如何編寫遞歸代碼？
關鍵是寫出遞歸公式，找到終止條件。
例：
假如有n個台階，每次你可以跨1個台階或者兩個台階，請問走完這n個台階有多少種走法？
實際上，我們可以根據第一步的走法把所有走法分為兩類：第一類是第一步走了一個台階，第二類是第一步走了兩個台階。是以用公式表示為： f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(n)=f(n-1)+f(n-2) f(n)=f(n−1)+f(n−2)
接下來看終止條件：當隻剩一個台階了，隻有一種走法, f ( 1 ) = 1 f(1)=1 f(1)=1。這個終止條件夠嗎？
我們用n=2,n=3這樣比較小的數試驗一下。
n=2時， f ( 2 ) = f ( 1 ) + f ( 0 ) f(2)=f(1)+f(0) f(2)=f(1)+f(0)。如果隻有上面一個終止條件， f ( 2 ) f(2) f(2)就無法求解了，還要有f(0)=1,表示0個台階有一種走法，但是這樣看起來就不符合正常的邏輯思維了。是以把 f ( 2 ) = 2 f(2)=2 f(2)=2作為一種終止條件。
所得到的遞歸公式和遞歸條件如下：
f ( 1 ) = 1 ; f ( 2 ) = 2 ; f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(1)=1;\\ f(2)=2; \\ f(n)=f(n-1)+f(n-2) f(1)=1;f(2)=2;f(n)=f(n−1)+f(n−2)
是以可以寫出代碼：
int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return f(n-1) + f(n-2);
}
寫遞歸代碼的關鍵就是找到如何将大問題分解為小問題的規律，并且基于此寫出遞推公式，然後再推敲終止條件，最後将遞推公式和終止條件翻譯成代碼。隻要遇到遞歸，我們就把它抽象成一個遞推公式，不用想一層層的調用關系，不要試圖用人腦去分解遞歸的每個步驟
3.1遞歸代碼要警惕堆棧溢出。
堆棧溢出會造成系統性崩潰。
在“棧”這節講過，函數調用會使用棧來儲存臨時變量，每調用一個函數都會将臨時變量封裝為棧幀壓入記憶體棧，等函數執行完成時才出棧。系統棧或者虛拟機棧空間一般都不大，如果遞歸求解的資料規模很大，調用層次很深，一直壓入棧就會有堆棧溢出的風險。
比如前面的講到的電影院的例子，如果我們将系統棧或者 JVM 堆棧大小設定為 1KB，在求解 f(19999) 時便會出現如下堆棧報錯：
Exception in thread "main" java.lang.StackOverflowError
如何避免出現堆棧溢出？
可以在代碼中限制遞歸調用的最大深度來解決這個問題，遞歸調用超過這個深度後就不往下再遞歸了，直接傳回報錯。如下方代碼：
// 全局變量，表示遞歸的深度。
int depth = 0;
int f(int n) {
++depth；
if (depth > 1000) throw exception;
if (n == 1) return 1;
return f(n-1) + 1;
}
但這種做法并不能完全解決問題，因為最大允許的遞歸深度跟目前線程剩餘的棧空間大小有關，事先無法計算。如果實時計算，代碼過于複雜，就會影響代碼的可讀性。是以，如果最大深度比較小，比如 10、50，就可以用這種方法，否則這種方法并不是很實用。規模大了，自己模拟一個棧，用非遞歸代碼實作。
3.2遞歸代碼要警惕重複計算
上台階的例子把整個遞歸過程分解一下，如下：
從圖中可以看到 f ( 3 ) f(3) f(3)被計算了很多次。
為了避免重複計算，我們可以通過一個資料結構（比如散清單）來儲存已經求解過的 f ( k ) f(k) f(k)。當遞歸調用到 f ( k ) f(k) f(k)時，先看下是否已經求解過了，如果是，直接從散清單中取值傳回。代碼如下：
public int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
// hasSolvedList可以了解成一個Map，key是n，value是f(n)
if (hasSolvedList.containsKey(n)) {
return hasSolvedList.get(n);
}
int ret = f(n-1) + f(n-2);
hasSolvedList.put(n, ret);
return ret;
}
3.3怎麼将遞歸代碼改寫為非遞歸代碼？
遞歸有利有弊，利是遞歸代碼表達力很強，寫起來很簡潔；弊就是空間複雜度高，有堆棧溢出的風險，存在重複計算，過多的函數調用會耗時較多等問題。
将遞歸代碼改寫為非遞歸代碼。
将 f ( x ) = f ( x − 1 ) + 1 f(x)=f(x-1)+1 f(x)=f(x−1)+1 的遞歸代碼改寫為非遞歸代碼如下：
int f(int n) {
int ret = 1;
for (int i = 2; i <= n; ++i) {
ret = ret + 1;
}
return ret;
}
第二個例子也可改寫為非遞歸的實作方式：
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;
}
是不是所有的遞歸代碼都可以改為這種疊代循環的非遞歸寫法？
籠統地講，是的。因為遞歸本身就是借助棧來實作的，隻不過我們使用的棧是系統或者虛拟機本身提供的，我們沒有感覺罷了。如果我們自己在記憶體堆上實作棧，手動模拟入棧、出棧過程，這樣任何遞歸代碼都可以改寫成看上去不是遞歸代碼的樣子。但是這種思路實際上是将遞歸改為了“手動”遞歸，本質并沒有變，而且也并沒有解決前面講到的某些問題，徒增了實作的複雜度。
4.解答開篇
如何找到“最終推薦人”？
long findRootReferrerId(long actorId) {
Long referrerId = select referrer_id from [table] where actor_id = actorId;
if (referrerId == null) return actorId;
return findRootReferrerId(referrerId);
}
代碼非常簡潔，幾行就搞定了。但是在實際項目中，這段代碼并不能工作。因為：
1.如果遞歸很深，可能會有堆棧溢出的問題。（限制遞歸深度來解決）
2。如果資料庫裡存在髒資料，我們還需要處理由此産生的無限遞歸問題。（可以用限制遞歸深度來解決，還有更進階的做法，即檢測"環"的存在。
遞歸代碼雖然簡潔高效，但是，遞歸代碼也有很多弊端。比如，堆棧溢出、重複計算、函數調用耗時多、空間複雜度高等，是以，在編寫遞歸代碼的時候，一定要控制好這些副作用。
5.課後思考
我們平時調試代碼喜歡使用 IDE 的單步跟蹤功能，像規模比較大、遞歸層次很深的遞歸代碼，幾乎無法使用這種調試方式。對于遞歸代碼，你有什麼好的調試方法呢
方法：
1.列印日志發現，遞歸值。
2.結合條件斷點進行調試。
6.參考
這個是我學習王争老師的《資料結構與算法之美》所做的筆記，王争老師是前谷歌工程師，該課程截止到目前已有87244人付費學習，品質不用多說。
截取了課程部分目錄，課程結合實際應用場景，從概念開始層層剖析，由淺入深進行講解。本人之前也學過許多資料結構與算法的課程，唯獨王争老師的課給我一種茅塞頓開的感覺，強烈推薦大家購買學習。課程二維碼我已放置在下方，大家想買的話可以掃碼購買。
本人做的筆記并不全面，推薦大家掃碼購買課程進行學習，而且課程非常便宜，學完後必有很大提高。