遞歸 & 分治演算法深度理解

首先簡單闡述一下遞歸,分治演算法,動態規劃,貪心演算法這幾個東西的區別和聯繫,心裡有個印象就好。

遞歸是一種編程技巧,一種解決問題的思維方式;分治演算法和動態規劃很大程度上是遞歸思想基礎上的(雖然實現動態規劃大都不是遞歸了,但是我們要注重過程和思想),解決更具體問題的兩類演算法思想;貪心演算法是動態規劃演算法的一個子集,可以更高效解決一部分更特殊的問題。

分治演算法將在這節講解,以最經典的歸併排序為例,它把待排序數組不斷二分為規模更小的子問題處理,這就是「分而治之」這個詞的由來。顯然,排序問題分解出的子問題是不重複的,如果有的問題分解後的子問題有重複的(重疊子問題性質),那麼這就交給動態規劃演算法去解決!

遞歸詳解

介紹分治之前,首先要弄清楚遞歸這個概念。

遞歸的基本思想是某個函數直接或者間接地調用自身,這樣就把原問題的求解轉換為許多性質相同但是規模更小的子問題。我們只需要關注如何把原問題劃分成符合條件的子問題,而不需要去研究這個子問題是如何被解決的。遞歸和枚舉的區別在於:枚舉是橫向地把問題劃分,然後依次求解子問題,而遞歸是把問題逐級分解,是縱向的拆分。

以下會舉例說明我對遞歸的一點理解, 如果你不想看下去了,請記住這幾個問題怎麼回答:

  1. 如何給一堆數字排序?答:分成兩半,先排左半邊再排右半邊,最後合併就行了,至於怎麼排左邊和右邊,請重新閱讀這句話。
  2. 孫悟空身上有多少根毛?答:一根毛加剩下的毛。
  3. 你今年幾歲?答:去年的歲數加一歲,1999 年我出生。

遞歸程式碼最重要的兩個特徵:結束條件和自我調用。自我調用是在解決子問題,而結束條件定義了最簡子問題的答案。

int func(傳入數值) {
  if (終止條件) return 最小子問題解;
  return func(縮小規模);
}

其實仔細想想, 遞歸運用最成功的是什麼?我認為是數學歸納法。 我們高中都學過數學歸納法,使用場景大概是:我們推不出來某個求和公式,但是我們試了幾個比較小的數,似乎發現了一點規律,然後猜想了一個公式,看起來應該是正確答案。但是數學是很嚴謹的,你哪怕窮舉了一萬個數都是正確的,但是第一萬零一個數正確嗎?這就要數學歸納法發揮神威了,可以假設我們猜想的這個公式在第 k 個數時成立,如果證明在第 k + 1 時也成立,那麼我們猜想的這個公式就是正確的。

那麼數學歸納法和遞歸有什麼聯繫?我們剛才說了,遞歸程式碼必須要有結束條件,如果沒有的話就會進入無窮無盡的自我調用,直到記憶體耗盡。而數學證明的難度在於,你可以嘗試有窮種情況,但是難以將你的結論延伸到無窮大。這裡就可以看出聯繫了——無窮。

遞歸程式碼的精髓在於調用自身去解決規模更小的子問題,直到到達結束條件;而數學歸納法之所以有用,就在於不斷把我們的猜測向上加一,擴大結論的規模,沒有結束條件,從而把結論延伸到無窮無盡,也就完成了猜測正確性的證明。

為什麼要寫遞歸

首先為了訓練逆向思考的能力。遞推的思維是正常人的思維,總是看著眼前的問題思考對策,解決問題是將來時;遞歸的思維,逼迫我們倒著思考,看到問題的盡頭,把解決問題的過程看做過去時。

第二,練習分析問題的結構,當問題可以被分解成相同結構的小問題時,你能敏銳發現這個特點,進而高效解決問題。

第三,跳出細節,從整體上看問題。再說說歸併排序,其實可以不用遞歸來劃分左右區域的,但是代價就是程式碼極其難以理解,大概看一下程式碼(歸併排序在後面講,這裡大致看懂意思就行,體會遞歸的妙處):

void sort(Comparable[] a){
    int N = a.length;
    // 這麼複雜,是對排序的不尊重。我拒絕研究這樣的程式碼。
    for (int sz = 1; sz < N; sz = sz + sz)
        for (int lo = 0; lo < N - sz; lo += sz + sz)
            merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
}

/* 我還是選擇遞歸,簡單,漂亮 */
void sort(Comparable[] a, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    sort(a, lo, mid);
    sort(a, mid + 1, hi);
    merge(a, lo, mid, hi);
}

看起來簡潔漂亮是一方面,關鍵是 可解釋性很強 :把左半邊排序,把右半邊排序,最後合併兩邊。而非遞歸版本看起來不知所云,充斥著各種難以理解的邊界計算細節,特別容易出 bug 且難以調試,人生苦短,我更傾向於遞歸版本。

顯然有時候遞歸處理是高效的,比如歸併排序, 有時候是低效的 ,比如數孫悟空身上的毛,因為堆棧會消耗額外空間,而簡單的遞推不會消耗空間。比如這個例子,給一個鏈表頭,計算它的長度:

/* 典型的遞推遍歷框架 */
public int size(Node head) {
    int size = 0;
    for (Node p = head; p != null; p = p.next) size++;
    return size;
}
/* 我偏要遞歸,萬物皆遞歸 */
public int size(Node head) {
    if (head == null) return 0;
    return size(head.next) + 1;
}

寫遞歸的技巧

我的一點心得是: 明白一個函數的作用並相信它能完成這個任務,千萬不要試圖跳進細節。 千萬不要跳進這個函數裡面企圖探究更多細節,否則就會陷入無窮的細節無法自拔,人腦能壓幾個棧啊。

先舉個最簡單的例子:遍歷二叉樹。

void traverse(TreeNode* root) {
  if (root == nullptr) return;
  traverse(root->left);
  traverse(root->right);
}

這幾行程式碼就足以掃蕩任何一棵二叉樹了。我想說的是,對於遞歸函數 traverse(root) ,我們只要相信:給它一個根節點 root ,它就能遍歷這棵樹,因為寫這個函數不就是為了這個目的嗎?所以我們只需要把這個節點的左右節點再甩給這個函數就行了,因為我相信它能完成任務的。那麼遍歷一棵 N 叉數呢?太簡單了好吧,和二叉樹一模一樣啊。

void traverse(TreeNode* root) {
  if (root == nullptr) return;
  for (child : root->children) traverse(child);
}

至於遍歷的什麼前、中、後序,那都是顯而易見的,對於 N 叉樹,顯然沒有中序遍歷。

以下 詳解 LeetCode 的一道題來說明 :給一棵二叉樹,和一個目標值,節點上的值有正有負,返回樹中和等於目標值的路徑條數,讓你編寫 pathSum 函數:

/* 來源於 LeetCode PathSum III: //leetcode.com/problems/path-sum-iii/ */
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11
/* 看不懂沒關係,底下有更詳細的分析版本,這裡突出體現遞歸的簡潔優美 */
int pathSum(TreeNode root, int sum) {
  if (root == null) return 0;
  return count(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
}
int count(TreeNode node, int sum) {
  if (node == null) return 0;
  return (node.val == sum) + count(node.left, sum - node.val) +
         count(node.right, sum - node.val);
}

題目看起來很複雜吧,不過程式碼卻極其簡潔,這就是遞歸的魅力。我來簡單總結這個問題的 解決過程

首先明確,遞歸求解樹的問題必然是要遍歷整棵樹的,所以 二叉樹的遍歷框架 (分別對左右孩子遞歸調用函數本身)必然要出現在主函數 pathSum 中。那麼對於每個節點,它們應該幹什麼呢?它們應該看看,自己和腳底下的小弟們包含多少條符合條件的路徑。好了,這道題就結束了。

按照前面說的技巧,根據剛才的分析來定義清楚每個遞歸函數應該做的事:

PathSum 函數:給它一個節點和一個目標值,它返回以這個節點為根的樹中,和為目標值的路徑總數。

count 函數:給它一個節點和一個目標值,它返回以這個節點為根的樹中,能湊出幾個以該節點為路徑開頭,和為目標值的路徑總數。

/* 有了以上鋪墊,詳細注釋一下程式碼 */
int pathSum(TreeNode root, int sum) {
  if (root == null) return 0;
  int pathImLeading = count(root, sum);  // 自己為開頭的路徑數
  int leftPathSum = pathSum(root.left, sum);  // 左邊路徑總數(相信他能算出來)
  int rightPathSum =
      pathSum(root.right, sum);  // 右邊路徑總數(相信他能算出來)
  return leftPathSum + rightPathSum + pathImLeading;
}
int count(TreeNode node, int sum) {
  if (node == null) return 0;
  // 我自己能不能獨當一面,作為一條單獨的路徑呢?
  int isMe = (node.val == sum) ? 1 : 0;
  // 左邊的小老弟,你那邊能湊幾個 sum - node.val 呀?
  int leftBrother = count(node.left, sum - node.val);
  // 右邊的小老弟,你那邊能湊幾個 sum - node.val 呀?
  int rightBrother = count(node.right, sum - node.val);
  return isMe + leftBrother + rightBrother;  // 我這能湊這麼多個
}

還是那句話, 明白每個函數能做的事,並相信它們能夠完成。

總結下,PathSum 函數提供的二叉樹遍歷框架,在遍歷中對每個節點調用 count 函數,看出先序遍歷了嗎(這道題什麼序都是一樣的);count 函數也是一個二叉樹遍歷,用於尋找以該節點開頭的目標值路徑。好好體會吧!

LeetCode 有遞歸專題練習, 點這裡去做題

遞歸優化

比較 naive 的遞歸實現可能遞歸次數太多,容易超時。

怎麼優化呢?可以使用 搜索優化記憶化搜索

分治演算法

歸併排序 ,典型的分治演算法;分治,典型的遞歸結構。

分治演算法可以分三步走:分解 -> 解決 -> 合併

  1. 分解原問題為結構相同的子問題。
  2. 分解到某個容易求解的邊界之後,進行遞歸求解。
  3. 將子問題的解合併成原問題的解。

歸併排序,我們就叫這個函數 merge_sort 吧,按照我們上面說的,要明確該函數的職責,即 對傳入的一個數組排序 。OK,那麼這個問題能不能分解呢?當然可以!給一個數組排序,不就等於給該數組的兩半分別排序,然後合併就完事了。

void merge_sort(一個數組) {
  if (可以很容易處理) return;
  merge_sort(左半個數組);
  merge_sort(右半個數組);
  merge(左半個數組, 右半個數組);
}

好了,這個演算法也就這樣了,完全沒有任何難度。記住之前說的,相信函數的能力,傳給它半個數組,那麼這半個數組就已經被排好了。而且你會發現這不就是個二叉樹遍歷模板嗎?為什麼是後序遍歷?因為我們分治演算法的套路是 分解 -> 解決(觸底)-> 合併(回溯) 啊,先左右分解,再處理合併,回溯就是在退棧,就相當於後序遍歷了。至於 merge 函數,參考兩個有序鏈表的合併,簡直一模一樣。

LeetCode 上有分治演算法的專項練習, 點這裡去做題

參考資料與注釋

  1. labuladong 的演算法小抄 – 遞歸詳解