溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
遞歸是算法中一種非常重要的思想，應用也很廣，小到階乘,再在工作中用到的比如統計文件夾大小，大到 Google 的 PageRank 算法都能看到，也是面試官很喜歡的考點
最近看了不少遞歸的文章，收獲不小，不過我發現大部分網上的講遞歸的文章都不太全面，主要的問題在于解題后大部分都沒有給出相應的時間/空間復雜度，而時間/空間復雜度是算法的重要考量!遞歸算法的時間復雜度普遍比較難（需要用到歸納法等），換句話說，如果能解決遞歸的算法復雜度，其他算法題題的時間復雜度也基本不在話下。另外，遞歸算法的時間復雜度不少是不能接受的，如果發現算出的時間復雜度過大，則需要轉換思路，看下是否有更好的解法 ，這才是根本目的，不要為了遞歸而遞歸！
本文試圖從以下幾個方面來講解遞歸
力爭讓大家對遞歸的認知能上一個新臺階，特別會對遞歸的精華:時間復雜度作詳細剖析，會給大家總結一套很通用的求解遞歸時間復雜度的套路，相信你看完肯定會有收獲
簡單地說，就是如果在函數中存在著調用函數本身的情況，這種現象就叫遞歸。
以階乘函數為例,如下, 在 factorial 函數中存在著 factorial(n - 1) 的調用，所以此函數是遞歸函數
public int factorial(int n) {
if (n < =1) {
return 1;
}
return n * factorial(n - 1)
}進一步剖析「遞歸」，先有「遞」再有「歸」，「遞」的意思是將問題拆解成子問題來解決， 子問題再拆解成子子問題，...，直到被拆解的子問題無需再拆分成更細的子問題（即可以求解），「歸」是說最小的子問題解決了，那么它的上一層子問題也就解決了，上一層的子問題解決了，上上層子問題自然也就解決了,....,直到最開始的問題解決,文字說可能有點抽象，那我們就以階層 f(6) 為例來看下它的「遞」和「歸」。
求解問題 f(6), 由于 f(6) = n f(5), 所以 f(6) 需要拆解成 f(5) 子問題進行求解，同理 f(5) = n f(4) ,也需要進一步拆分,... ,直到 f(1), 這是「遞」，f(1) 解決了，由于 f(2) = ?2 f(1) = 2 也解決了,.... f(n)到最后也解決了，這是「歸」，所以遞歸的本質是能把問題拆分成具有相同解決思路的子問題，。。。直到最后被拆解的子問題再也不能拆分，解決了最小粒度可求解的子問題后，在「歸」的過程中自然順其自然地解決了最開始的問題。
我們在上一節仔細剖析了什么是遞歸，可以發現遞歸有以下兩個特點
所以解遞歸題的關鍵在于我們首先需要根據以上遞歸的兩個特點判斷題目是否可以用遞歸來解。
經過判斷可以用遞歸后，接下來我們就來看看用遞歸解題的基本套路（四步曲）：
聽起來是不是很簡單，接下來我們就由淺入深地來看幾道遞歸題，看下怎么用上面的幾個步驟來套
輸入一個正整數n，輸出n!的值。其中n!=123…n,即求階乘
套用上一節我們說的遞歸四步解題套路來看看怎么解
/**
* 求 n 的階乘
*/
public int factorial(int n) {
}
將第二步的遞推公式用代碼表示出來補充到步驟 1 定義的函數中
/**
* 求 n 的階乘
*/
public int factorial(int n) {
// 第二步的臨界條件
if (n < =1) {
return 1;
}
// 第二步的遞推公式
return n * factorial(n-1)
}看起來是不是有這么點眉目， 當然這道題確實太過簡單,很容易套路，那我們再來看進階一點的題
一只青蛙可以一次跳 1 級臺階或一次跳 2 級臺階,例如:
跳上第 1 級臺階只有一種跳法：直接跳 1 級即可。跳上第 2 級臺階
有兩種跳法：每次跳 1 級，跳兩次；或者一次跳 2 級。
問要跳上第 n 級臺階有多少種跳法？
我們繼續來按四步曲來看怎么套路
/**
* 跳 n 極臺階的跳法
*/
public int f(int n) {
}
/**
* 跳 n 極臺階的跳法
*/
public int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return f(n-1) + f(n-2)
}
斐波那契的時間復雜度計算涉及到高等代數的知識， 這里不做詳細推導,我們直接結出結論
由些可知時間復雜度是指數級別，顯然不可接受，那回過頭來看為啥時間復雜度這么高呢,假設我們要計算 f(6),根據以上推導的遞歸公式，展示如下
可以看到有大量的重復計算, f(3) 計算了 3 次， 隨著 n 的增大，f(n) 的時間復雜度自然呈指數上升了
既然有這么多的重復計算，我們可以想到把這些中間計算過的結果保存起來，如果之后的計算中碰到同樣需要計算的中間態，直接在這個保存的結果里查詢即可，這就是典型的?以空間換時間,改造后的代碼如下
public int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
// map 即保存中間態的鍵值對， key 為 n，value 即 f(n)
if (map.get(n)) {
return map.get(n)
}
return f(n-1) + f(n-2)
}那么改造后的時間復雜度是多少呢，由于對每一個計算過的 f(n) 我們都保存了中間態 ，不存在重復計算的問題，所以時間復雜度是 O(n), 但由于我們用了一個鍵值對來保存中間的計算結果，所以空間復雜度是 O(n)。問題到這里其實已經算解決了，但身為有追求的程序員，我們還是要問一句,空間復雜度能否繼續優化?
使用循環迭代來改造算法 我們在分析問題與子問題關系（f(n) = f(n-1) + f(n-2)）的時候用的是自頂向下的分析方式,但其實我們在解 f(n) 的時候可以用自下而上的方式來解決，通過觀察我們可以發現以下規律
f(1) = 1
f(2) = 2
f(3) = f(1) + f(2) = 3
f(4) = f(3) + f(2) = 5
....
f(n) = f(n-1) + f(n-2)最底層 f(1), f(2) 的值是確定的，之后的 f(3), f(4) ,...等問題都可以根據前兩項求解出來，一直到 f(n)。所以我們的代碼可以改造成以下方式
public int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
int result = 0;
int pre = 1;
int next = 2;
for (int i = 3; i < n + 1; i ++) {
result = pre + next;
pre = next;
next = result;
}
return result;
}改造后的時間復雜度是 O(n), 而由于我們在計算過程中只定義了兩個變量（pre，next），所以空間復雜度是O(1)
簡單總結一下：分析問題我們需要采用自上而下的思維，而解決問題有時候采用自下而上的方式能讓算法性能得到極大提升,思路比結論重要
接下來我們來看下一道經典的題目: 反轉二叉樹 將左邊的二叉樹反轉成右邊的二叉樹
接下來讓我們看看用我們之前總結的遞歸解法四步曲如何解題?
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}public TreeNode invertTree(TreeNode root) {
}
- 查找問題與子問題的關系,得出遞推公式 我們之前說了，解題要采用自上而下的思考方式，那我們取前面的1， 2，3 結點來看，對于根節點 1 來說，假設 2, 3 結點下的節點都已經翻轉，那么只要翻轉 2， 3 節點即滿足需求
對于2， 3 結點來說，也是翻轉其左右節點即可,依此類推,對每一個根節點，依次翻轉其左右節點，所以我們可知問題與子問題的關系是 翻轉(根節點) = ?翻轉(根節點的左節點) + 翻轉(根節點的右節點) 即?invert(root) = invert(root->left) + invert(root->right)
而顯然遞歸的終止條件是當結點為葉子結點時終止（因為葉子節點沒有左右結點）
- 將第二步的遞推公式用代碼表示出來補充到步驟 1 定義的函數中public TreeNode invertTree(TreeNode root) {
// 葉子結果不能翻轉
if (root == null) {
return null;
}
// 翻轉左節點下的左右節點
TreeNode left = invertTree(root.left);
// 翻轉右節點下的左右節點
TreeNode right = invertTree(root.right);
// 左右節點下的二叉樹翻轉好后，翻轉根節點的左右節點
root.right = left;
root.left = right;
return root;}
- 時間復雜度分析 由于我們會對每一個節點都去做翻轉，所以時間復雜度是 O(n)，那么空間復雜度呢，這道題的空間復雜度非常有意思，我們一起來看下，由于每次調用 invertTree 函數都相當于一次壓棧操作， 那最多壓了幾次棧呢， 仔細看上面函數的下一段代碼TreeNode left = invertTree(root.left);從根節點出發不斷對左結果調用翻轉函數, 直到葉子節點，每調用一次都會壓棧，左節點調用完后，出棧，再對右節點壓棧....,下圖可知棧的大小為3， 即樹的高度，如果是完全二叉樹 ，則樹的高度為logn, 即空間復雜度為O(logn)
最壞情況，如果此二叉樹是如圖所示(只有左節點，沒有右節點)，則樹的高度即結點的個數 n，此時空間復雜度為 O(n),總的來看，空間復雜度為O(n)
說句題外話，這道題當初曾引起轟動，因為 Mac 下著名包管理工具 homebrew ?的作者 Max Howell 當初解不開這道題，結果被 Google 拒了，也就是說如果你解出了這道題，就超越了這位世界大神，想想是不是很激動
#### **中級題**
接下來我們看一下大學時學過的漢諾塔問題： 如下圖所示，從左到右有A、B、C三根柱子，其中A柱子上面有從小疊到大的n個圓盤，現要求將A柱子上的圓盤移到C柱子上去，期間只有一個原則：一次只能移到一個盤子且大盤子不能在小盤子上面，求移動的步驟和移動的次數
接下來套用我們的遞歸四步法看下這題怎么解
- 定義問題的遞歸函數，明確函數的功能,我們定義這個函數的功能為：把 A 上面的 n 個圓盤經由 B 移到 C// 將 n 個圓盤從 a 經由 b 移動到 c 上
public void hanoid(int n, char a, char b, char c) {
}
- 查找問題與子問題的關系 首先我們看如果 A 柱子上只有兩塊圓盤該怎么移
前面我們多次提到，分析問題與子問題的關系要采用自上而下的分析方式，要將 n 個圓盤經由 B 移到 C 柱上去，可以按以下三步來分析 * 將 上面的 n-1 個圓盤看成是一個圓盤,這樣分析思路就與上面提到的只有兩塊圓盤的思路一致了 * 將上面的 ?n-1 個圓盤經由 C 移到 B * 此時將 A 底下的那塊最大的圓盤移到 C * 再將 B 上的 n-1 個圓盤經由A移到 C上
有人問第一步的 n - 1 怎么從 C 移到 B,重復上面的過程,只要把 上面的 n-2個盤子經由 A 移到 B, 再把A最下面的盤子移到 C,最后再把上面的 n - 2 的盤子經由A 移到 B 下..., 怎么樣，是不是找到規律了，不過在找問題的過程中?**切忌把子問題層層展開**,到漢諾塔這個問題上切忌再分析 n-3,n-4 怎么移，這樣會把你繞暈，只要找到一層問題與子問題的關系得出可以用遞歸表示即可。
由以上分析可得move(n from A to C) = move(n-1 from A to B) + move(A to C) + move(n-1 from B to C`)
一定要先得出遞歸公式，哪怕是偽代碼也好!這樣第三步推導函數編寫就容易很多，終止條件我們很容易看出，當 A 上面的圓盤沒有了就不移了
- 根據以上的遞歸偽代碼補充函數的功能// 將 n 個圓盤從 a 經由 b 移動到 c 上
public void hanoid(int n, char a, char b, char c) {
if (n <= 0) {
return;
}
// 將上面的 n-1 個圓盤經由 C 移到 B
hanoid(n-1, a, c, b);
// 此時將 A 底下的那塊最大的圓盤移到 C
move(a, c);
// 再將 B 上的 n-1 個圓盤經由A移到 C上
hanoid(n-1, b, a, c);
}
public void move(char a, char b) {
printf("%c->%c\n", a, b);
}
**從函數的功能**上看其實比較容易理解，整個函數定義的功能就是把 A 上的 n 個圓盤 經由 B 移到 C，由于定義好了這個函數的功能，那么接下來的把 n-1 個圓盤 經由 C 移到 B 就可以很自然的調用這個函數,所以**明確函數的功能非常重要**,按著函數的功能來解釋，遞歸問題其實很好解析，**切忌在每一個子問題上層層展開死摳**,這樣這就陷入了遞歸的陷阱，計算機都會棧溢出，何況人腦
- 時間復雜度分析 從第三步補充好的函數中我們可以推斷出
f(n) = f(n-1) + 1 + f(n-1) = 2f(n-1) + 1 = 2(2f(n-2) + 1) + 1 = 2 * 2 * f(n-2) + 2 + 1 = 2<sup>2</sup>?* f(n-3) + 2 + 1 = 2<sup>2</sup>?* f(n-3) + 2 + 1 = ?2<sup>2</sup>?* (2f(n-4) + 1) = 2<sup>3</sup>?* f(n-4) + 2<sup>2</sup>??+ 1 = .... ? ? ? ?// 不斷地展開 = 2<sup>n-1</sup>?+ 2<sup>n-2</sup>?+ ....+ 1
顯然時間復雜度為 O(2<sup>n</sup>)，很明顯指數級別的時間復雜度是不能接受的，漢諾塔非遞歸的解法比較復雜，大家可以去網上搜一下
#### **進階題**
現實中大廠中的很多遞歸題都不會用上面這些相對比較容易理解的題，更加地是對遞歸問題進行相應地變形， 來看下面這道題
> 細胞分裂 有一個細胞 每一個小時分裂一次，一次分裂一個子細胞，第三個小時后會死亡。那么n個小時候有多少細胞？
照樣我們用前面的遞歸四步曲來解
- 定義問題的遞歸函數，明確函數的功能 我們定義以下函數為 n 個小時后的細胞數public int allCells(int n) {
}
- 接下來尋找問題與子問題間的關系（即**遞推公式**） 首先我們看一下一個細胞出生到死亡后經歷的所有細胞分裂過程
圖中的 A 代表細胞的初始態, B代表幼年態(細胞分裂一次), C 代表成熟態(細胞分裂兩次)，C 再經歷一小時后細胞死亡 以 f(n) 代表第 n 小時的細胞分解數 f<sub>a</sub>(n) 代表第 n 小時處于初始態的細胞數, f<sub>b</sub>(n) 代表第 n 小時處于幼年態的細胞數 f<sub>c</sub>(n) 代表第 n 小時處于成熟態的細胞數 則顯然 f(n) = ?f<sub>a</sub>(n) ?+ f<sub>b</sub>(n) ?+ f<sub>c</sub>(n) 那么 f<sub>a</sub>(n) 等于多少呢，以n = 4 （即一個細胞經歷完整的生命周期）為例
仔細看上面的圖
可以看出 f<sub>a</sub>(n) ?= f<sub>a</sub>(n-1) + f<sub>b</sub>(n-1) + f<sub>c</sub>(n-1), 當 n = 1 時，顯然 f<sub>a</sub>(1) = 1
f<sub>b</sub>(n) 呢,看下圖可知 f<sub>b</sub>(n) ?= f<sub>a</sub>(n-1)。當 n = 1 時 ?f<sub>b</sub>(n) = 0
f<sub>c</sub>(n) 呢,看下圖可知 ?f<sub>c</sub>(n) ?= f<sub>b</sub>(n-1)。當 n = 1,2 時 f<sub>c</sub>(n) = 0
綜上， 我們得出的遞歸公式如下
- 根據以上遞歸公式我們補充一下函數的功能public int allCells(int n) {
return aCell(n) + bCell(n) + cCell(n);
}
/**
/**
/**
只要思路對了，將遞推公式轉成代碼就簡單多了，另一方面也告訴我們，可能一時的遞歸關系我們看不出來，此時可以借助于畫圖來觀察規律之前青蛙跳臺階時間復雜度是指數級別的，而這個方程式顯然比之前的遞推公式(f(n) = f(n-1) + f(n-2)) 更復雜的，所以顯然也是指數級別的
大部分遞歸題其實還是有跡可尋的， 按照之前總結的解遞歸的四個步驟可以比較順利的解開遞歸題，一些比較復雜的遞歸題我們需要勤動手，畫畫圖，觀察規律，這樣能幫助我們快速發現規律，得出遞歸公式，一旦知道了遞歸公式，將其轉成遞歸代碼就容易多了,很多大廠的遞歸考題并不能簡單地看出遞歸規律，往往會在遞歸的基礎上多加一些變形，不過萬遍不離其宗，我們多采用自頂向下的分析思維，多練習，相信遞歸不是什么難事
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
