遞歸 & 分治

本頁面將介紹遞歸與分治算法的區別與結合運用。

遞歸

定義

遞歸（英語：Recursion），在數學和計算機科學中是指在函數的定義中使用函數自身的方法，在計算機科學中還額外指一種通過重複將問題分解為同類的子問題而解決問題的方法。

引入

要理解遞歸，就得先理解什麼是遞歸。

遞歸的基本思想是某個函數直接或者間接地調用自身，這樣原問題的求解就轉換為了許多性質相同但是規模更小的子問題。求解時只需要關注如何把原問題劃分成符合條件的子問題，而不需要過分關注這個子問題是如何被解決的。

以下是一些有助於理解遞歸的例子：

1. 什麼是遞歸？
2. 如何給一堆數字排序？答：分成兩半，先排左半邊再排右半邊，最後合併就行了，至於怎麼排左邊和右邊，請重新閲讀這句話。
3. 你今年幾歲？答：去年的歲數加一歲，1999 年我出生。
4. 

遞歸在數學中非常常見。例如，集合論對自然數的正式定義是：1 是一個自然數，每個自然數都有一個後繼，這一個後繼也是自然數。

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

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

為什麼要寫遞歸

1. 結構清晰，可讀性強。例如，分別用不同的方法實現 歸併排序：

   C++Python

   // 不使用遞歸的歸併排序算法
   template <typename T>
   void merge_sort(vector<T> a) {
     int n = a.size();
     for (int seg = 1; seg < n; seg = seg + seg)
       for (int start = 0; start < n - seg; start += seg + seg)
         merge(a, start, start + seg - 1, std::min(start + seg + seg - 1, n - 1));
   }
   
   // 使用遞歸的歸併排序算法
   template <typename T>
   void merge_sort(vector<T> a, int front, int end) {
     if (front >= end) return;
     int mid = front + (end - front) / 2;
     merge_sort(a, front, mid);
     merge_sort(a, mid + 1, end);
     merge(a, front, mid, end);
   }
   

   # 不使用遞歸的歸併排序算法
   def merge_sort(a):
     n = len(a)
     seg, start = 1, 0
     while seg < n:
         while start < n - seg:
             merge(a, start, start + seg - 1, min(start + seg + seg - 1, n - 1))
             start = start + seg + seg
         seg = seg + seg
   
   # 使用遞歸的歸併排序算法
   def merge_sort(a, front, end):
     if front >= end:
         return
     mid = front + (end - front) / 2
     merge_sort(a, front, mid)
     merge_sort(a, mid + 1, end)
     merge(a, front, mid, end)
   

   顯然，遞歸版本比非遞歸版本更易理解。遞歸版本的做法一目瞭然：把左半邊排序，把右半邊排序，最後合併兩邊。而非遞歸版本看起來不知所云，充斥着各種難以理解的邊界計算細節，特別容易出 bug，且難以調試。

2. 練習分析問題的結構。當發現問題可以被分解成相同結構的小問題時，遞歸寫多了就能敏鋭發現這個特點，進而高效解決問題。

遞歸的缺點

在程序執行中，遞歸是利用堆棧來實現的。每當進入一個函數調用，棧就會增加一層棧幀，每次函數返回，棧就會減少一層棧幀。而棧不是無限大的，當遞歸層數過多時，就會造成 棧溢出 的後果。

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

// 典型的遞推遍歷框架
int size(Node *head) {
  int size = 0;
  for (Node *p = head; p != nullptr; p = p->next) size++;
  return size;
}

// 我就是要寫遞歸，遞歸天下第一
int size_recursion(Node *head) {
  if (head == nullptr) return 0;
  return size_recursion(head->next) + 1;
}

遞歸的優化

主頁面：搜索優化 和 記憶化搜索

比較初級的遞歸實現可能遞歸次數太多，容易超時。這時需要對遞歸進行優化。¹

分治

定義

分治（英語：Divide and Conquer），字面上的解釋是「分而治之」，就是把一個複雜的問題分成兩個或更多的相同或相似的子問題，直到最後子問題可以簡單的直接求解，原問題的解即子問題的解的合併。

過程

分治算法的核心思想就是「分而治之」。

大概的流程可以分為三步：分解 -> 解決 -> 合併。

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

分治法能解決的問題一般有如下特徵：

• 該問題的規模縮小到一定的程度就可以容易地解決。
• 該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質，利用該問題分解出的子問題的解可以合併為該問題的解。
• 該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。

注意

如果各子問題是不獨立的，則分治法要重複地解公共的子問題，也就做了許多不必要的工作。此時雖然也可用分治法，但一般用 動態規劃 較好。

以歸併排序為例。假設實現歸併排序的函數名為 merge_sort。明確該函數的職責，即 對傳入的一個數組排序。這個問題顯然可以分解。給一個數組排序等於給該數組的左右兩半分別排序，然後合併成一個數組。

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

傳給它半個數組，那麼處理完後這半個數組就已經被排好了。注意到，merge_sort 與二叉樹的後序遍歷模板極其相似。因為分治算法的套路是 分解 -> 解決（觸底）-> 合併（回溯），先左右分解，再處理合併，回溯就是在退棧，即相當於後序遍歷。

merge 函數的實現方式與兩個有序鏈表的合併一致。

要點

寫遞歸的要點

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

以遍歷二叉樹為例。

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

這幾行代碼就足以遍歷任何一棵二叉樹了。對於遞歸函數 traverse(root)，只要相信給它一個根節點 root，它就能遍歷這棵樹。所以只需要把這個節點的左右節點再傳給這個函數就行了。

同樣擴展到遍歷一棵 N 叉樹。與二叉樹的寫法一模一樣。不過，對於 N 叉樹，顯然沒有中序遍歷。

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

區別

遞歸與枚舉的區別

遞歸和枚舉的區別在於：枚舉是橫向地把問題劃分，然後依次求解子問題；而遞歸是把問題逐級分解，是縱向的拆分。

遞歸與分治的區別

遞歸是一種編程技巧，一種解決問題的思維方式；分治算法很大程度上是基於遞歸的，解決更具體問題的算法思想。

例題詳解

437. 路徑總和 III

給定一個二叉樹，它的每個結點都存放着一個整數值。

找出路徑和等於給定數值的路徑總數。

路徑不需要從根節點開始，也不需要在葉子節點結束，但是路徑方向必須是向下的（只能從父節點到子節點）。

二叉樹不超過 1000 個節點，且節點數值範圍是 [-1000000,1000000] 的整數。

示例：

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

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

返回 3。和等於 8 的路徑有：

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

/**
 * 二叉樹結點的定義
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

參考代碼

int pathSum(TreeNode *root, int sum) {
  if (root == nullptr) return 0;
  return count(root, sum) + pathSum(root->left, sum) +
         pathSum(root->right, sum);
}

int count(TreeNode *node, int sum) {
  if (node == nullptr) 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 == nullptr) 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 == nullptr) return 0;
  // 能不能作為一條單獨的路徑呢？
  int isMe = (node->val == sum) ? 1 : 0;
  // 左邊的，你那邊能湊幾個 sum - node.val ？
  int leftNode = count(node->left, sum - node->val);
  // 右邊的，你那邊能湊幾個 sum - node.val ？
  int rightNode = count(node->right, sum - node->val);
  return isMe + leftNode + rightNode;  // 我這能湊這麼多個
}

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

總結下，PathSum 函數提供了二叉樹遍歷框架，在遍歷中對每個節點調用 count 函數（這裏用的是先序遍歷，不過中序遍歷和後序遍歷也可以）。count 函數也是一個二叉樹遍歷，用於尋找以該節點開頭的目標值路徑。

習題

• LeetCode 上的遞歸專題練習
• LeetCode 上的分治算法專項練習

參考資料與註釋

---

1. labuladong 的算法小抄 - 遞歸詳解 ↩

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：fudonglai, AngelKitty, labuladong
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用