遞歸是算法學習中很基本也很常用的一種方法，但是對于初學者來說比較難以了解（PS：難點在于不斷調用自身，産生多個傳回值，理不清其傳回值的具體順序，以及最終的傳回值到底是哪一個？）。是以，本文将選擇LeetCode中一些比較經典的習題，通過簡單測試執行個體，具體講解遞歸的實作原理。本文要講的内容包括以下幾點：
- 了解遞歸的運作原理
- 求解遞歸算法的時間複雜度和空間複雜度
- 如何把遞歸用到解題中（尋找遞推關系，或者遞推公式）
- 記憶化操作
- 尾遞歸
- 剪枝操作
了解遞歸的運作原理
例1求解斐波那契數列
題目描述（題目序号：509，困難等級：簡單）：
求解代碼（基礎版）：
class Solution {
public int fib(int N) {
if(N <= 1)
return N;
return fib(N - 1) + fib(N - 2);
}
} 現在以N = 5為例，分析上述代碼的運作原理，具體如下圖：
遞歸的傳回值很多，初學者很難了解最終的傳回值是哪個，此時可以采用上圖的方式畫一個樹形圖，手動執行遞歸代碼，樹形圖的葉節點即為遞歸的終止條件，樹形圖的根節點即為最終的傳回值。樹形圖的所有節點個數即為遞歸程式得到最終傳回值的總體運作次數，可以借此計算時間複雜度，這個問題會在後文講解。
例2 二叉樹的三種周遊方式
二叉樹的周遊方式一般有四種：前序周遊、中序周遊、後序周遊和層次周遊，前三種周遊方式應用遞歸可以大大減少代碼量，而層次周遊一般應用隊列方法（即非遞歸方式）求解。以下将要講解應用遞歸求解二叉樹的前、中、後序周遊的實作原理。
前序周遊
前序周遊方式：根節點->左子樹->右子樹。
題目描述（題目序号：144，困難等級：中等）：
求解代碼：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null)
return list;
List<Integer> left = preorderTraversal(root.left);
List<Integer> right = preorderTraversal(root.right);
list.add(root.val);
for(Integer l: left)
list.add(l);
for(Integer r: right)
list.add(r);
return list;
}
} 具體測試執行個體如下圖：
中序周遊
中序周遊方式：左子樹->根節點->右子樹。
題目描述（題目序号：94，困難等級：中等）：
求解代碼：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null)
return list;
List<Integer> left = inorderTraversal(root.left);
List<Integer> right = inorderTraversal(root.right);
for(Integer l: left)
list.add(l);
list.add(root.val);
for(Integer r: right)
list.add(r);
return list;
}
} 具體測試執行個體如下圖：
後序周遊
後序周遊方式：左子樹->右子樹->根節點。
題目描述（題目序号：145，困難等級：困難）：
求解代碼：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null)
return list;
List<Integer> left = postorderTraversal(root.left);
List<Integer> right = postorderTraversal(root.right);
for(Integer l: left)
list.add(l);
for(Integer r: right)
list.add(r);
list.add(root.val);
return list;
}
} 具體測試執行個體如下圖：
例3求解二叉樹的最近公共祖先
題目描述（題目序号：236，困難等級：中等）：
求解思路：
遞歸終止條件：
(1) 根節點為空
(2) 根節點為指定的兩個節點之一
遞歸方式：
在根節點的左子樹中尋找最近公共祖先。
在根節點的右子樹中尋找最近公共祖先。
如果左子樹和右子樹傳回值均不為空，說明兩個節點分别在左右子樹，最終傳回root。
如果左子樹為空，說明兩個節點均在右子樹，最終傳回右子樹的傳回值。
如果右子樹為空，說明兩個節點均在左子樹，最終傳回左子樹的傳回值。
如果左子樹和右子樹均為空，說明該次沒有比對的結果。
具體代碼如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return root;
}
if (root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) {
return root;
} else if (left != null) {
return left;
} else if (right != null) {
return right;
}
return null;
}
} 具體測試執行個體如下圖：
求解遞歸算法的時間複雜度和空間複雜度
以上一節例1斐波那契數列為例。
時間複雜度
時間複雜度一般可以了解為程式運作調用的次數。在應用遞歸解題過程中，如果目前遞歸運作過程中，相關求解過程的運作時間不受變量影響，且運作時間是常數量級，則該算法的時間複雜度為遞歸的總體傳回次數。
以上一節例1中解題思路，求解fib(5)總共return15次，畫的樹形圖包含5層。那麼求解例1中示例解答程式代碼的時間複雜度，就是求解樹形圖的整體節點個數。對于n層滿二叉樹，共有2^n – 1個節點，是以求解fib(n)，大約需要傳回(2^n - 1)次，才能得到最終的根節點值。那麼，fib(n)的時間複雜度為O(2^n)。
空間複雜度
遞歸算法的空間複雜度一般與遞歸的深度有關。一般來說，如果目前遞歸運作過程中，消耗的空間複雜度是一個常數，那麼該算法的最終空間複雜度即為遞歸的深度。計算方式：遞歸的深度*一次遞歸的空間複雜度。
遞歸的運作狀态，随着運作深度的增加，系統會把上一次的狀态存入系統棧中，一旦遇到遞歸終止條件，便開始不斷出棧，直到棧為空時，程式結束。是以，遞歸程式的空間複雜度一般和遞歸的深度有關。
以上一節例1中解題思路，求解fib(5)時，需要最深的層次需要經曆以下過程：
第一層：fib(5) = fib(4) + fib(3)
第二層：fib(4) = fib(3) + fib(2)
第三層：fib(3) = fib(2) + fib(1)
第四層：fib(2) = fib(1) + fib(0)
第五層：fib(1)，遇到遞歸終止條件，開始進行出棧操作。
可知求解fib(5)時，遞歸的深度為5，具體可對照例1中畫的二叉樹，正好等于二叉樹的高度。那麼求解fib(n)的空間複雜度為O(n)。
如何把遞歸用到解題中（尋找遞推關系，或者遞推公式）
例4字元串的反轉
題目描述（題目序号：344，困難等級：簡單）：
遞推關系：reverse(s[0,n]) = reverse(s[1,n-1])
具體代碼如下：
class Solution {
public void reverseString(char[] s) {
dfs(s, 0, s.length-1);
}
public void dfs(char[] s, int start, int end) {
if(start > end)
return;
dfs(s, start+1, end-1);
char temp = s[start];
s[start] = s[end];
s[end] = temp;
}
} 例5兩兩交換連結清單中的節點
題目描述（題目序号：24，困難等級：中等）：
遞推關系：swapPairs(head) = swapPairs(head.next.next)
具體代碼如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode next = head.next;
head.next = swapPairs(next.next);
next.next = head;
return next;
}
} 例6 所有可能的滿二叉樹
題目描述（題目序号：894，困難等級：中等）：
遞推關系: allPossibleFBT(N) = allPossibleFBT(i) + allPossibleFBT(N – 1 - i)，其中i為奇數，1<= i<N。
具體代碼如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<TreeNode> allPossibleFBT(int N) {
List<TreeNode> ans = new ArrayList<>();
if (N % 2 == 0) {
return ans;
}
if (N == 1) {
TreeNode head = new TreeNode(0);
ans.add(head);
return ans;
}
for (int i = 1; i < N; i += 2) {
List<TreeNode> left = allPossibleFBT(i);
List<TreeNode> right = allPossibleFBT(N - 1 - i);
for (TreeNode l : left) {
for (TreeNode r : right) {
TreeNode head = new TreeNode(0);
head.left = l;
head.right = r;
ans.add(head);
}
}
}
return ans;
}
} 記憶化操作
由第一節例1的解答代碼可知，求解fib(n)的時間複雜度為O(2^n)，其中進行了大量重複求值過程，比如求解fib(5)時，需要求解兩次fib(3)，求解三次fib(2)等。那麼如何避免重複求解的過程呢？我們可以采用記憶化操作。
記憶化操作就是把之前遞歸求解得到的傳回值儲存到一個全局變量中，後面遇到對應的參數值，先判斷目前全局變量中是否包含其解，如果包含則直接傳回具體解，否則進行遞歸求解。
例1：
原解答代碼：
class Solution {
public int fib(int N) {
if(N <= 1)
return N;
return fib(N - 1) + fib(N - 2);
}
} 時間複雜度為O(2^n),空間複雜度為O(n)。送出測試結果：
采用記憶化改進：
class Solution {
private Map<Integer, Integer> map = new HashMap<>();
public int fib(int N) {
if(N <= 1)
return N;
if(map.containsKey(N))
return map.get(N);
int result = fib(N - 1) + fib(N - 2);
map.put(N, result);
return result;
}
} 具體遞歸應用測試示例如下圖：
時間複雜度為O(n),空間複雜度為O(n)。送出測試結果：
求解斐波那契數列，還有多種方法，比如矩陣乘法、數學公式直接計算等。是以，采用記憶化改進的代碼并不是最優，這點在本文不作詳細讨論。
尾遞歸
尾遞歸是指在傳回時，直接傳回遞歸函數調用的值，不做額外的運算。比如，第一節中斐波那契數列的遞歸是傳回: return fib(N-1) + fib(N-2);。傳回時，需要做加法運算，這樣的遞歸調用就不屬于尾遞歸。
下面解釋引用自LeetCode解答
尾遞歸的好處是，它可以避免遞歸調用期間棧空間開銷的累積，因為系統可以為每個遞歸調用重用棧中的固定空間。
在尾遞歸的情況下，一旦從遞歸調用傳回，我們也會立即傳回，是以我們可以跳過整個遞歸調用傳回鍊，直接傳回到原始調用方。這意味着我們根本不需要所有遞歸調用的調用棧，這為我們節省了空間。
尾遞歸的優勢可以通俗的了解為：降低算法的空間複雜度，由原來應用棧存儲中間狀态，變換為不斷直接傳回最終值。
通常，編譯器會識别尾遞歸模式，并優化其執行。然而，并不是所有的程式設計語言都支援這種優化，比如 C，C++ 支援尾遞歸函數的優化。另一方面，Java 和 Python 不支援尾遞歸優化。
剪枝操作
剪枝操作是指在遞歸調用過程中，通過添加相關判斷條件，減少不必要的遞歸操作，進而提高算法的運作速度。一般來說，良好的剪枝操作能夠降低算法的時間複雜度，提高程式的健壯性。下面将以一道算法題來說明。
題目描述（題目序号：698，困難等級：中等）：
解題思路：
首先，對原始數組進行從小到大排序操作。
然後，初始化長度為K的數組，每一個元素指派為sum(nums) / K。
最後，從排序後的數組的最後一個元素開始進行遞歸操作。依次，選擇長度為K的數組中每個元素減去數組中的元素，如果相減的差為0或者小于0則跳過，否則執行正常的相減操作。
剪枝政策：
（1） 如果數組nums中最大元素大于sum(nums) / K，則直接傳回，結束程式。
（2） 如果執行目前減法操作得到的結果小于nums數組中最小值，則放棄本次遞歸操作，進行下一次遞歸操作。
具體實作代碼如下（包含剪枝）：
class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = 0;
for(int i = 0; i < nums.length; i++){
sum += nums[i];
}
if(sum % k != 0){
return false;
}
sum = sum / k;
Arrays.sort(nums);
if(nums[nums.length - 1] > sum){
return false;
}
int[] arr = new int[k];
Arrays.fill(arr, sum);
return help(nums, nums.length - 1, arr, k);
}
boolean help(int[] nums, int cur, int[] arr, int k){
if(cur < 0){
return true;
}
for(int i = 0; i < k; i++){
//如果正好能放下目前的數或者放下目前的數後，還有機會繼續放前面的數（剪枝）
if(arr[i] == nums[cur] || (arr[i] - nums[cur] >= nums[0])){
arr[i] -= nums[cur];
//遞歸，開始放下一個數
if(help(nums, cur - 1, arr, k)){
return true;
}
arr[i] += nums[cur];
}
}
return false;
}
} 測試結果：
将剪枝操作删除，變成正常的遞歸調用，即把下述代碼：
//如果正好能放下目前的數或者放下目前的數後，還有機會繼續放前面的數（剪枝）
if(arr[i] == nums[cur] || (arr[i] - nums[cur] >= nums[0])){ 變換成：
if(arr[i] >= nums[cur]){ 測試結果：
由上述對比分析可知，靈活運用剪枝操作可以有效提高程式的運作效率。