關(guān)注公眾號 碼哥字節(jié)，設(shè)置星標獲取最新推送。后臺回復(fù) “加群” 進入技術(shù)交流群獲更多技術(shù)成長。

摘要：遞歸是一種應(yīng)用非常廣泛的算法（或者編程技巧）。之后我們要講的很多數(shù)據(jù)結(jié)構(gòu)和算法的編碼實現(xiàn)都要用到遞歸，比如 DFS 深度優(yōu)先搜索、前中后序二叉樹遍歷等等。所以，搞懂遞歸非常重要，否則，后面復(fù)雜一些的數(shù)據(jù)結(jié)構(gòu)和算法學(xué)起來就會比較吃力

推薦用戶注冊領(lǐng)取傭金很多人都遇到過，很多 App 在推廣的時候都是這個套路?！甘捄巍挂]「韓信」加入劉邦陣營，「韓信」又引薦了那些年上鋪的兄弟「韓大膽」加入。我們就可以認為「韓大膽」的最終推薦人是「蕭何」，「韓信」的最終推薦人是「蕭何」，而「蕭何」沒有最終推薦人。

用數(shù)據(jù)庫記錄他們之間的關(guān)系，soldier_id 表示士兵 id，referrer_id 表示推薦人 id。

那么問題來了，給定一個士兵 id，如何查找這個用戶的「最終推薦人」，帶著這個問題，我們正式進入遞歸。

遞歸三要素

有兩個最難理解的知識點，一個是 動態(tài)規(guī)劃，一個是遞歸。

大學(xué)軍訓(xùn)，都會經(jīng)歷過排隊報數(shù)，報數(shù)過程中自己開小差看見了一個漂亮小學(xué)姐，不知道旁邊的哥們剛說的數(shù)字，所以再問一下左邊哥們剛報了多少，只要在他說的數(shù)字 + 1 就知道自己樹第幾個了，關(guān)鍵是現(xiàn)在你旁邊的哥們 看見漂亮小學(xué)姐竟然忘記剛剛自己說的數(shù)字了，也要繼續(xù)問他左邊的老鐵，就這樣一直往前問，直到第一個報數(shù)的孩子，然后一層層把數(shù)字傳遞到自己。

這就是一個非常標準的遞歸求解過程，問的過程叫「遞」，回來的過程交「歸」。轉(zhuǎn)換成遞推公式：

f(n)=f(n-1) + 1, 存在 f(1) = 1

f(n) 表示自己的數(shù)字，f(n - 1) 表示前面一個人的報數(shù)，f(1) 表示第一個人知道自己是第一個報的數(shù)字。

根據(jù)遞推公式，很容易的轉(zhuǎn)換成遞歸代碼：

public int f(int n) {
  if (n == 1) return 1;
  return f(n-1) + 1;
}

到底什么問題可以用遞歸解決呢？總結(jié)了三個必要元素，只要滿足一下三個條件，就可以使用遞歸解決。

1.一個問題可以分解多個子問題

就是可以分解恒數(shù)字規(guī)模更小的問題，比如要知道自己的報數(shù)，可以分解『前一個人的報數(shù)』這樣的子問題。

2.問題本身與分解后的子問題，除了數(shù)據(jù)規(guī)模不同，求解算法相同

『求解自己的報數(shù)』和前面一個人『求解自己的報數(shù)』思路是一模一樣。

3.存在遞歸終止條件

問題分解成子問題的過程中，不能出現(xiàn)無限循環(huán)，所以需要一個終止條件，就像第一排或者其中任何一個知道自己報數(shù)的孩子不需要再詢問上一個人的數(shù)字，f(1) = 1 就是遞歸終止條件。

如何編寫遞歸代碼

其實最關(guān)鍵的就是 寫出遞推公式，找到終止條件，然后把遞推公式轉(zhuǎn)成 代碼就容易多了。

再舉一個「青蛙跳臺階」的算法問題，假設(shè)有 n 個臺階，每次可以跳 1 個或者 2 個臺階，走這 n 個臺階有多少種走法？

再仔細想想，實際上，根據(jù)第一步的走法可以把所有的走法分兩類，第一類是第一步走了 1 個臺階，另一種是第一步走了 2 個臺階。所以 n 個臺階的走法就等于先走 1 階后， n-1 個臺階的走法 + 先走 2 階后， n-2 個臺階的走法。

f(n) = f(n-1) + f(n-2)

繼續(xù)分析終止條件，當只有一個臺階的時候不需要再繼續(xù)遞歸，f (1) = 1。似乎還不夠，假如有兩個臺階呢？分別用 n = 2、n=3 驗證下。f(2) = 2 也是終止條件之一。

所以該遞歸的終止條件就是 f(1) = 1,f(2) = 2。

f(1) = 1;
f(2) = 2;
f(n) = f(n-1) + f(n-2);

根據(jù)公式轉(zhuǎn)成代碼則是

public int f(n) {
  if(n == 1) return 1;
  if(n ==2) return 2;
  return f(n-1) + f(n-2);
}

劃重點了：寫遞歸大媽的關(guān)鍵就是找到如何將大問題分解成小問題的規(guī)律，并且基于此寫出遞推公式，再推出終止條件，租后將地推公式和終止條件翻譯成代碼。

對于遞歸代碼，我們不要試圖去弄清楚整個遞和歸的問題，這個不適合我們的正常思維，我們大腦更適合平鋪直敘的思維，當看到遞歸切勿妄想把遞歸過程平鋪展開，否則會陷入一層一層往下調(diào)用的循環(huán)。

當遇到一個問題 1 可以分解若干個 2,3,4 問題，我們只要假設(shè) 2,3,4 已經(jīng)解決，在此基礎(chǔ)上思考如何解決 A。這樣就容易多了。

所以當遇到遞歸，編寫 代碼的關(guān)鍵就是 把問題抽象成一個遞推公式，不要想一層層的調(diào)用關(guān)系，找到終止條件。

防止棧溢出

遞歸最大的問題就是要防止棧溢出以及死循環(huán)。為何遞歸容易造成棧溢出呢？我們回想下之前說過的棧數(shù)據(jù)結(jié)構(gòu)，不清楚的朋友可以翻閱歷史文章。函數(shù)調(diào)用會使用棧來保存臨時變量，每次調(diào)用一個函數(shù)都會把臨時變量封裝成棧幀壓入線程對應(yīng)的棧中，等方法結(jié)束返回時，才出棧。如果遞歸的數(shù)據(jù)規(guī)模比較大，調(diào)用層次很深就會導(dǎo)致一直壓入棧，而棧的大小通常不會很大就會導(dǎo)致堆棧溢出的情況。

Exception in thread "main" java.lang.StackOverflowError

如何防止呢？

我們只能在代碼里面限制最大深度，直接返回錯誤，使用一個全局變量表示遞歸的深度，每次執(zhí)行都 + 1，當超過指定閾值還沒有結(jié)束的時候直接返回錯誤。

警惕重復(fù)計算

青蛙跳臺階的問題就有重復(fù)計算的問題，我們試著把遞歸過程分解下，想要計算 f(5)，需要先計算 f(4) 和 f(3)，而計算 f(4) 還需要計算 f(3)，因此，f(3) 就被計算了很多次，這就是重復(fù)計算問題。為了避免重復(fù)計算，我們可以通過一個數(shù)據(jù)結(jié)構(gòu)（比如 HashMap）來保存已經(jīng)求解過的 f(k)。當遞歸調(diào)用到 f(k) 時，先看下是否已經(jīng)求解過了。如果是，則直接從散列表中取值返回，不需要重復(fù)計算，這樣就能避免剛講的問題了。

public int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;

  // hasSolvedList 可以理解成一個 Map，key 是 n，value 是 f(n)
  if (hasSolvedMap.containsKey(n)) {
    return hasSovledMap.get(n);
  }

  int ret = f(n-1) + f(n-2);
  hasSovledMap.put(n, ret);
  return ret;
}

遞歸的空間復(fù)雜度因為每次調(diào)用都會在棧上保存一次臨時變量，所以它的空間復(fù)雜度就是 O(N),而不是 O(1)。

如何將遞歸轉(zhuǎn)換成非遞歸代碼

遞歸有利有弊，遞歸寫起來很簡潔，而不好的地方就是空間復(fù)雜度是 O(n)，有堆棧溢出風險，存在重復(fù)計算。要根具體情況來選擇是否需要遞歸。

還是軍訓(xùn)排隊報數(shù)的例子，如何變成非遞歸。

f(n) = f(n-1) +1;

public int f(n) {
  int r = 1;
  for(int i = 2; i <= n; i++) {
    r += 1;
  }
  return r;
}

對于臺階問題也是可以改成循環(huán)實現(xiàn)。

public 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èi)绾谓獯痖_篇的問題：根據(jù)士兵 id 找到最佳推薦人？

public int findRootReferId(int soldierId) {
  Integer referId = "select reference_id from [table] where soldier_id = soldierId";
  if (referId == null) return soldierId;
  return findRootReferId(referId);
}

遞歸是一種非常高效、簡潔的編碼技巧。只要是滿足“三個條件”的問題就可以通過遞歸代碼來解決。

不過遞歸代碼也比較難寫、難理解。編寫遞歸代碼的關(guān)鍵就是不要把自己繞進去，正確姿勢是寫出遞推公式，找出終止條件，然后再翻譯成遞歸代碼。

遞歸代碼雖然簡潔高效，但是，遞歸代碼也有很多弊端。比如，堆棧溢出、重復(fù)計算、函數(shù)調(diào)用耗時多、空間復(fù)雜度高等，所以，在編寫遞歸代碼的時候，一定要控制好這些副作用。

碼哥字節(jié)

推薦閱讀

1.跨越數(shù)據(jù)結(jié)構(gòu)與算法

2.時間復(fù)雜度與空間復(fù)雜度

3.最好、最壞、平均、均攤時間復(fù)雜度

4.線性表之數(shù)組

5.鏈表導(dǎo)論-心法篇

6.單向鏈表正確實現(xiàn)方式

7.雙向鏈表正確實現(xiàn)

8.棧實現(xiàn)瀏覽器的前進后退

9.隊列-生產(chǎn)消費模式

原創(chuàng)不易，覺得有用希望隨手「在看」「收藏」「轉(zhuǎn)發(fā)」三連。