作者 | kunge
責編 | Elle
前言
遞歸是算法中一種非常重要的思想，應用也很廣，小到階乘,再在工作中用到的比如統計檔案夾大小，大到 Google 的 PageRank 算法都能看到，也是面試官很喜歡的考點
最近看了不少遞歸的文章，收獲不小，不過我發現大部分網上的講遞歸的文章都不太全面，主要的問題在于解題後大部分都沒有給出相應的時間/空間複雜度，而時間/空間複雜度是算法的重要考量!遞歸算法的時間複雜度普遍比較難(需要用到歸納法等)，換句話說，如果能解決遞歸的算法複雜度，其他算法題題的時間複雜度也基本不在話下。另外，遞歸算法的時間複雜度不少是不能接受的，如果發現算出的時間複雜度過大，則需要轉換思路，看下是否有更好的解法 ，這才是根本目的，不要為了遞歸而遞歸！
本文試圖從以下幾個方面來講解遞歸
- 什麼是遞歸？
- 遞歸算法通用解決思路
- 實戰演練(從初級到高階)
力争讓大家對遞歸的認知能上一個新台階，特别會對遞歸的精華:時間複雜度作詳細剖析，會給大家總結一套很通用的求解遞歸時間複雜度的套路，相信你看完肯定會有收獲
什麼是遞歸
簡單地說，就是如果在函數中存在着調用函數本身的情況，這種現象就叫遞歸。
以階乘函數為例,如下, 在 factorial 函數中存在着 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)到最後也解決了，這是「歸」，是以遞歸的本質是能把問題拆分成具有相同解決思路的子問題，。。。直到最後被拆解的子問題再也不能拆分，解決了最小粒度可求解的子問題後，在「歸」的過程中自然順其自然地解決了最開始的問題。
遞歸算法通用解決思路
我們在上一節仔細剖析了什麼是遞歸，可以發現遞歸有以下兩個特點
- 一個問題可以分解成具有相同解決思路的子問題，子子問題，換句話說這些問題都能調用同一個函數
- 經過層層分解的子問題最後一定是有一個不能再分解的固定值的(即終止條件),如果沒有的話,就無窮無盡地分解子問題了，問題顯然是無解的。
是以解遞歸題的關鍵在于我們首先需要根據以上遞歸的兩個特點判斷題目是否可以用遞歸來解。
經過判斷可以用遞歸後，接下來我們就來看看用遞歸解題的基本套路(四步曲)：
- 先定義一個函數，明确這個函數的功能，由于遞歸的特點是問題和子問題都會調用函數自身，是以這個函數的功能一旦确定了， 之後隻要找尋問題與子問題的遞歸關系即可
- 接下來尋找問題與子問題間的關系(即遞推公式)，這樣由于問題與子問題具有相同解決思路，隻要子問題調用步驟 1 定義好的函數，問題即可解決。所謂的關系最好能用一個公式表示出來，比如 f(n) = n * f(n-) 這樣，如果暫時無法得出明确的公式，用僞代碼表示也是可以的, 發現遞推關系後，要尋找最終不可再分解的子問題的解，即(臨界條件)，確定子問題不會無限分解下去。由于第一步我們已經定義了這個函數的功能，是以當問題拆分成子問題時，子問題可以調用步驟 1 定義的函數，符合遞歸的條件(函數裡調用自身)
- 将第二步的遞推公式用代碼表示出來補充到步驟 1 定義的函數中
- 最後也是很關鍵的一步，根據問題與子問題的關系，推導出時間複雜度,如果發現遞歸時間複雜度不可接受，則需轉換思路對其進行改造，看下是否有更靠譜的解法
聽起來是不是很簡單，接下來我們就由淺入深地來看幾道遞歸題，看下怎麼用上面的幾個步驟來套
實戰演練(從初級到高階)
熱身賽
輸入一個正整數n，輸出n!的值。其中n!=123*…*n,即求階乘
套用上一節我們說的遞歸四步解題套路來看看怎麼解
- 定義這個函數，明确這個函數的功能，我們知道這個函數的功能是求 n 的階乘, 之後求 n-1, n-2 的階乘就可以調用此函數了
2.尋找問題與子問題的關系階乘的關系比較簡單， 我們以 f(n) 來表示 n 的階乘， 顯然 f(n) = n * f(n - 1), 同時臨界條件是 f(1) = 1,即
3.将第二步的遞推公式用代碼表示出來補充到步驟 1 定義的函數中
4.求時間複雜度由于 f(n) = n * f(n-1) = n * (n-1) * .... * f(1),總共作了 n 次乘法，是以時間複雜度為 n。
看起來是不是有這麼點眉目， 當然這道題确實太過簡單,很容易套路，那我們再來看進階一點的題
入門題
一隻青蛙可以一次跳 1 級台階或一次跳 2 級台階,例如:跳上第 1 級台階隻有一種跳法：直接跳 1 級即可。跳上第 2 級台階有兩種跳法：每次跳 1 級，跳兩次；或者一次跳 2 級。問要跳上第 n 級台階有多少種跳法？
我們繼續來按四步曲來看怎麼套路
1.定義一個函數，這個函數代表了跳上 n 級台階的跳法
2.尋找問題與子問題之前的關系這兩者之前的關系初看确實看不出什麼頭緒，但仔細看題目，一隻青蛙隻能跳一步或兩步台階，自上而下地思考，也就是說如果要跳到 n 級台階隻能從 從 n-1 或 n-2 級跳， 是以問題就轉化為跳上 n-1 和 n-2 級台階的跳法了，如果 f(n) 代表跳到 n 級台階的跳法，那麼從以上分析可得 f(n) = f(n-1) + f(n-2),顯然這就是我們要找的問題與子問題的關系,而顯然當 n = 1, n = 2， 即跳一二級台階是問題的最終解，于是遞推公式系為
3.将第二步的遞推公式用代碼表示出來補充到步驟 1 定義的函數中補充後的函數如下
4.計算時間複雜度由以上的分析可知f(n) 滿足以下公式
斐波那契的時間複雜度計算涉及到高等代數的知識， 這裡不做詳細推導，有興趣的同學可以點選這裡檢視,我們直接結出結論
由些可知時間複雜度是指數級别，顯然不可接受，那回過頭來看為啥時間複雜度這麼高呢,假設我們要計算 f(6),根據以上推導的遞歸公式，展示如下
可以看到有大量的重複計算, f(3) 計算了 3 次， 随着 n 的增大，f(n) 的時間複雜度自然呈指數上升了
5.優化
既然有這麼多的重複計算，我們可以想到把這些中間計算過的結果儲存起來，如果之後的計算中碰到同樣需要計算的中間态，直接在這個儲存的結果裡查詢即可，這就是典型的 以空間換時間,改造後的代碼如下
那麼改造後的時間複雜度是多少呢，由于對每一個計算過的 f(n) 我們都儲存了中間态 ，不存在重複計算的問題，是以時間複雜度是 O(n), 但由于我們用了一個鍵值對來儲存中間的計算結果，是以空間複雜度是 O(n)。問題到這裡其實已經算解決了，但身為有追求的程式員，我們還是要問一句,空間複雜度能否繼續優化?
6.使用循環疊代來改造算法我們在分析問題與子問題關系(f(n) = f(n-1) + f(n-2))的時候用的是自頂向下的分析方式,但其實我們在解 f(n) 的時候可以用自下而上的方式來解決，通過觀察我們可以發現以下規律
最底層 f(1), f(2) 的值是确定的，之後的 f(3), f(4) ,...等問題都可以根據前兩項求解出來，一直到 f(n)。是以我們的代碼可以改造成以下方式
改造後的時間複雜度是 O(n), 而由于我們在計算過程中隻定義了兩個變量(pre，next)，是以空間複雜度是O(1)
簡單總結一下：分析問題我們需要采用自上而下的思維，而解決問題有時候采用自下而上的方式能讓算法性能得到極大提升,思路比結論重要
初級題
接下來我們來看下一道經典的題目: 反轉二叉樹将左邊的二叉樹反轉成右邊的二叉樹
接下來讓我們看看用我們之前總結的遞歸解法四步曲如何解題
1.定義一個函數，這個函數代表了翻轉以 root 為根節點的二叉樹
2.查找問題與子問題的關系,得出遞推公式我們之前說了，解題要采用自上而下的思考方式，那我們取前面的1， 2，3 結點來看，對于根節點 1 來說，假設 2, 3 結點下的節點都已經翻轉，那麼隻要翻轉 2， 3 節點即滿足需求
對于2， 3 結點來說，也是翻轉其左右節點即可,依此類推,對每一個根節點，依次翻轉其左右節點，是以我們可知問題與子問題的關系是翻轉(根節點) = 翻轉(根節點的左節點) + 翻轉(根節點的右節點)即
invert(root) = invert(root->left) + invert(root->right)
而顯然遞歸的終止條件是當結點為葉子結點時終止(因為葉子節點沒有左右結點)
3.将第二步的遞推公式用代碼表示出來補充到步驟 1 定義的函數中
4.時間複雜度分析由于我們會對每一個節點都去做翻轉，是以時間複雜度是 O(n)，那麼空間複雜度呢，這道題的空間複雜度非常有意思，我們一起來看下，由于每次調用 invertTree 函數都相當于一次壓棧操作， 那最多壓了幾次棧呢， 仔細看上面函數的下一段代碼
從根節點出發不斷對左結果調用翻轉函數, 直到葉子節點，每調用一次都會壓棧，左節點調用完後，出棧，再對右節點壓棧....,下圖可知棧的大小為3， 即樹的高度，如果是完全二叉樹 ，則樹的高度為logn, 即空間複雜度為O(logn)
最壞情況，如果此二叉樹是如圖所示(隻有左節點，沒有右節點)，則樹的高度即結點的個數 n，此時空間複雜度為 O(n),總的來看，空間複雜度為O(n)
說句題外話，這道題當初曾引起轟動，因為 Mac 下著名包管理工具 homebrew 的作者 Max Howell 當初解不開這道題，結果被 Google 拒了，也就是說如果你解出了這道題，就超越了這位世界大神，想想是不是很激動
中級題
接下來我們看一下大學時學過的漢諾塔問題： 如下圖所示，從左到右有A、B、C三根柱子，其中A柱子上面有從小疊到大的n個圓盤，現要求将A柱子上的圓盤移到C柱子上去，期間隻有一個原則：一次隻能移到一個盤子且大盤子不能在小盤子上面，求移動的步驟和移動的次數
接下來套用我們的遞歸四步法看下這題怎麼解
1.定義問題的遞歸函數，明确函數的功能,我們定義這個函數的功能為：把 A 上面的 n 個圓盤經由 B 移到 C
2.查找問題與子問題的關系首先我們看如果 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 上面的圓盤沒有了就不移了
3.根據以上的遞歸僞代碼補充函數的功能