遞歸算法

遞歸是一種應用非常廣泛的算法（或者編程技巧）。也是很多數據結構和算法編碼實現的基礎。比如DFS深度優先搜索、前中后序二叉樹遍歷等等，所以搞懂遞歸是學習后面復雜的數據結構和算法的前提條件。

1. 理解遞歸

遞歸在我們的生活中也是很常見的：

在電影院里，在漆黑的時候，我們沒法直接知道自己是第幾排，于是我們就可以問前一排的人他是第幾排，我們只要在前一個人的基礎加一，但前面一排的人也看不清楚，所以他也要問他前面的人。就這樣一排一排往前問，直到問到第一排的人，因為第一排的人本身就知道自己是第一排，然后再這樣一排一排的把數字傳回來。直到你前面的人告訴你他在哪一排，于是就知道你自己是第幾排了。

上面的例子是一個非常標準的遞歸求解問題的分解過程，去的過程叫“遞”，回來的過程叫“歸”。

遞歸問題幾乎都可以用遞推公式來表示。上面電影院的例子的是：

                    f(n)=f(n-1)+1 其中，f(1)=1

f(n)表示你想知道自己在哪一排，f(n-1)表示前面一排所在的排數，f(1)=1表示第一排的人知道自己在第一排。

根據上面的遞推公式，我們就可以寫出遞推代碼：

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

2. 遞歸需滿足的三個條件

只有同時滿足下面三個條件的問題，才能用遞歸來解決。

1. 一個問題的解可以分解為幾個子問題的解

何為子問題？子問題就是數據規模更小的問題。比如前面電影院的例子，你要知道"自己在哪一排"的問題，可以分解為"前一排的人在哪一排"這樣的子問題。

2. 這個問題與分解之后的子問題，除了數據規模不同，求解思路完全一樣

比如電影院的例子，你求解"自己在哪一排"的思路，和前面一排人求解"自己在哪一排"的思路，是一模一樣的。

3. 存在遞歸終止條件

把問題分解為子問題，再把子問題分解為子子問題，一層一層分解下去，不能存在無限循環，這就需要有終止條件。

比如電影院的例子，第一排的人不需要在繼續詢問任何人，就知道自己在哪一排，也就是f(1)=1，這就是遞歸的終止條件。

3. 如何編寫遞歸代碼

寫遞歸代碼最關鍵的是"寫出遞推公式，找到終止條件"，然后就是將遞推公式轉化為代碼。

為了理解上面的結論，我們舉例說明：

假如有n個臺階，每次你可以跨1個臺階或2個臺階，請問走這n個臺階有多少種走法？

如果共有7個臺階，可以是 2 2 2 1，也可以是 1 2 1 1 2 等等。走法有多種，但如何用編程求解總共有多少種走法呢？

可以根據第一步的走法把所有走法分為兩類：

第一類：第一步走了1個臺階

第二類：第一步走了2個臺階

所以n個臺階的走法就等于先走1個臺階后，n-1個臺階的走法加上先走2個臺階后，n-2個臺階的走法，所以遞推公式就是：

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

有了遞推公式，然后就需要找到終止條件。

當只剩一個臺階時，不需要遞推，因為走法就只有一種，即f(1)=1。

當還剩兩個臺階時，這時候可以一步走完（直接跨兩個臺階），或者一步一步的走（每次跨一個臺階），即f(2)=2。

當還剩三個臺階時，可以分解為上面兩個子問題，即f(3)=f(2)+f(1)。

。。。以此類推。。。

所以終止條件就是f(1)=1,f(2)=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);
}

總結：寫遞歸代碼的關鍵就是找到如何將大問題分解為小問題的規律，并且基于此寫出遞推公式，然后再推敲終止條件，最后將遞推公式和終止條件翻譯成代碼。

前面電影院的例子，遞歸調用只有一個分支，即：一個問題只需要分解為一個子問題。這種情況，我們很容易理解，也能夠想清楚"遞"和"歸"的每一個步驟，所以想起來、理解起來都不難。

但當一個問題要分解為多個子問題的時候，遞歸代碼就沒那么好理解。例如上面走臺階的例子，我們幾乎不能將整個"遞"和"歸"的過程一步一步都想清楚。

其實，對于遞歸代碼，我們試圖想弄清楚整個"遞"和"歸"過程的做法，實際上是一個進入了思維誤區。很多時候，我們理解起來很費力，主要原因是我們自己給自己制造了這種理解障礙。

我們正確的理解方式應該是：

如果一個問題A可以分解為若干子問題B、C、D，你可以先假設子問題B、C、D已經解決，在此基礎上思考如何解決問題A。你只需要思考A與子問題B、C、D兩層之間的關系即可，不需要一層一層往下思考子問題與子子問題，子子問題與子子子問題之間的關系。屏蔽掉遞歸細節，這樣就容易理解很多。

因此，編寫遞歸代碼的關鍵是，只要遇到遞歸，就把它想象成一個遞推公式，不用想一層層的調用關系，不要試圖用人腦去解遞歸的每個步驟。

4. 警惕堆棧溢出

在寫遞歸代碼時，容易堆棧溢出，堆棧溢出會導致系統崩潰，后果很嚴重。

遞歸代碼容易造成堆棧溢出的原因

函數調用會使用棧來保存臨時變量，每調用一個函數，都會將臨時變量封裝為棧幀壓入內存棧，等函數執行完成返回時，才出棧。系統棧或者虛擬機棧空間一般都不大，如果遞歸求解的數據規模很大，調用層次很深，一直壓入棧，就會有堆棧溢出的風險。

比如前面電影院的例子，如果我們將系統棧或者JVM堆棧大小設置為1KB，在求解f(19999)時便會出現如下堆棧報錯：

Exception in thread "main" java.lang.StackOverflowError

遞歸代碼中如何預防堆棧溢出

可以通過在代碼中限制遞歸調用的最大深度來解決堆棧溢出的問題。一般遞歸深度超過1000后，就不繼續往下遞歸，直接返回報錯。

例如電影院的例子，我們可以通過如下改造，就可以避免堆棧溢出。

// 全局變量，表示遞歸的深度。
int depth = 0;

int f(int n) {
  ++depth；
  if (depth > 1000) throw exception;

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

上面寫的是偽代碼，為了代碼簡潔，有些邊界條件沒有考慮，比如x<=0。

但這種做法并不能完全解決問題，因為最大允許的遞歸深度跟當前線程剩余的棧空間大小有關，事先無法計算。如果實時計算，代碼就會過于復雜，會影響代碼的可讀性。所以，如果最大深度比較小，比如50、100，就可以用這種方法，否則這種方法并不是很實用。

5. 警惕重復計算

在使用遞歸時，還會出現重復計算的問題。上面講的臺階的例子，如果我們將整個遞歸過程分解一下的話，就如下圖所示：

從圖中可以看出，當我們計算f(5)時，需要先計算f(4)和f(3)，而計算f(4)時，還需要計算f(3)，因此，f(3)就會計算多次，這就是重復計算問題。

為了避免重復計算，可以通過一個數據結構（比如散列表）來保存已經求解過的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 hasSovledList.get(n);
  }

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

在時間效率上，遞歸代碼里多了很多函數調用，當這些函數調用的數量較大時，就會積聚成一個較大的時間成本。在空間復雜度上，因為遞歸調用一次就會在內存棧中保存一次現場數據，所以在分析遞歸代碼空間復雜度時，需要額外的考慮這部分開銷，例如上面電影院的例子，空間復雜度并不是O(1)，而是O(n)。

6. 將遞歸代碼改為非遞歸代碼

遞歸代碼有利有弊：

利：

代碼簡潔、表達能力強

弊：

空間復雜度高、有堆棧溢出的風險、存在重復計算、過多的函數調用會耗時較多。

所以在實際開發過程中，我們需要根據實際情況來選擇是否用遞歸的方式去實現。

我們也可以將遞歸代碼改為非遞歸代碼，例如電影院的例子就可修改為如下：

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;
}

理論上講，所有的遞歸代碼都可以改為這種迭代循環的非遞歸寫法。

7. 內容小結

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

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

• 遞歸代碼雖然簡潔高效，但是也有很多弊端，例如：堆棧溢出、重復計算、函數調用耗時多、空間復雜度高等。