数据结构与算法之递归系列
本文來自一個不甘平凡的碼農
寫在前邊
幾個月之前就想寫這樣一篇文章分享給大家，由于自己有心而力不足，沒有把真正的學到的東西沉淀下來，所以一直在不斷的在自學。
然后又用了一個星期的時間去整理、分類，才有了這篇 8000 字有關遞歸的分享，希望能夠幫助正在學習遞歸的小伙伴們，這篇文章是縮減版，可以點擊“閱讀原文”查看完整版。
而且有了這篇文章的支撐和動力，往后還會寫出關于數據結構與算法一些難懂的概念簡單化。如果文章中有錯誤的地方，希望大家指正，能夠為他人分享出更有質量的文章！
接下來分享的文章是關于遞歸的，這篇文章不單單分享遞歸的一切，我覺得更重要的是向每位讀者傳遞一個思想。思想？對的，沒錯！這篇文章不能說包含遞歸的邊邊角角，但是通過自己的理論上的學習和實踐，有了自己的一套遞歸思想。
什么問題該用遞歸，什么問題用遞歸簡潔，什么問題就不能使用遞歸解決，以及對于特定的問題用遞歸解決的陷阱，能不能進一步對遞歸進行二次優化，這些都是今天小鹿分享的內容。
什么是遞歸
遞歸，顧名思義，有遞有歸才叫遞歸，有遞無歸，有歸無遞那叫 “耍流氓” 。
為什么要學習遞歸
我們學習一門技術也好，編程語言也好，首先學習之前我們知道它將能給我們帶來什么，能幫助我們解決什么樣的問題，這也是激勵我們去學習它的動力所在。
從數組到鏈表、散列表，再到基本算法等，直到遇到遞歸之后，感覺非常的難理解。我相信每個人都有這種感覺，一開始覺得非常難，經歷了九九八十一難之后，還是沒有弄懂遞歸里邊的貓膩，然后就自然而然的跳過了。
后來我就開始刷了一個月的 LeetCode 題，發現遞歸在數據結構與算法中有著一席之地，統治著江山。大部分的題都可以用遞歸去解決，如：二叉樹的遍歷、回溯算法、0-1 背包問題、深度優先遍歷、回溯算法等等，我整理了至少二三十到關于遞歸的題，才發現遞歸的重要性，所以不得不重新深入遞歸學習，所有有了今天這篇文章。
如何理解遞歸
上方我對遞歸“耍流氓”式的定義并不能讓你準確的理解遞歸是什么，那么我們就來活生生的舉個生活中的例子。
1、問題
比如你和小鹿我一樣，在大學里喜歡插隊打飯（作為一個三好學生，我怎么能干這種事呢？哈哈），那么隊伍后邊的同學本數著自己前邊還有 5 個同學就改輪到自己了，由于前邊同學不斷的插隊，這時他發現，怎么覺得自己離著打飯的窗口越來越遠呢？這時如果他想知道自己在隊隊列中的的第幾個（前提是前邊不再有人插隊），用遞歸思想來解決，我們怎么做呢？
2、“遞”
于是他問前邊的同學是第幾位，前邊的同學也不只到呀，于是前邊的同學問他前邊的同學是第幾位，直到前邊第二個同學問到第一個正在打飯的同學是隊伍的第幾個（有點小尷尬）。打飯的同學不耐煩的說，沒看到我是第一個正在打飯嗎？這個過程其實是就是一個遞歸中“遞”的過程。
3、“歸”
然后前邊打飯的第二個同學不耐煩的又告訴第三個同學，我是第二個，沒看單我前邊有個家伙正在打飯嗎？然后第三個傳給第四個，以后往后傳，直到那位逐漸遠離窗口的同學的前一個人告訴他是第幾個之后，他知道了自己目前在隊伍中的第幾個位置。這個過程我們可以理解為遞歸中“歸”的過程。
4、終止條件
“打飯的同學不耐煩的說，沒看到我是第一個正在打飯嗎？”，在遞歸中，我們稱為終止條件。
5、怎么理解遞歸
問題雖然是層層遞歸的分析，但是用程序表示的時候，不要層層的在大腦中調用遞歸代碼去想，這樣可能會使你完全陷入到 “遞” 的過程中去，“歸” 的時候，歸不出來了，這些都是我們交給計算機干的事情。
那我們在寫程序的時候怎么理解遞歸呢？我們只找問題之間存在的關系，屏蔽掉遞歸的細節，具體看（五）分析。
滿足遞歸的條件
什么樣的問題才能滿足用遞歸解決呢？具有什么樣的特征，有沒有判斷條件？
1、一個問題能不能分解成多個子問題來解決
想知道自己在隊伍中的位置，將其問題分解為“每個人所處隊伍中的位置”這樣的多個子問題。
2、該問題是否和子問題的解決方法相同
想要知道自己當前的位置，就要問前邊人所處的位置。那么前邊人想要知道自己所處的位置，就要知道他前邊人的位置。所以說，該問題和子問題的解決思路相同，滿足第二個條件。
3、該問題是否有終止條件
第一個正在打飯的同學說自己是隊伍中的第一人，這就是所謂的終止條件，找到終止條件之后就開始進行“歸”的過程。
遞歸的分類
通過做大量的題，根據遞歸解決不同的問題，引申出來的幾種解決和思考的方式。之所以將其分類，是為了能夠更好的理解遞歸在不同的問題下起著什么作用，如：每層遞歸之間存在的關系、計算，以及遞歸枚舉所有情況和面臨選擇性問題的遞歸。雖然分為了幾類，但是遞歸的本質是一成不變的。
※ 分類一：遞歸計算型
1、層層計算
層層計算，顧名思義，能夠用遞歸解決的問題都可以分為多個子問題，我們把每個子問題可以抽象成一層，子問題之間的關系可以表示為層與層之間的關系。我們通過層與層之間的計算關系用遞推公式表達出來做計算，經過層層的遞歸，最終得到結果值。
▉ 例子：
我們再那上方排隊打飯的例子來說明，我們的子問題已經分析出來了，就是我想知道當前在隊伍中的位置，就是去問我前邊人的位置加一就是我當前隊伍的位置，這為一層。而前邊這個人想知道當前自己的位置，需要用同樣的解決思路，作為另一層。
層與層之間的關系是什么（我當前隊伍中的位置與前邊人的位置存在什么樣的關系）？這時你會說，當前是 +1。這個大部分人都很容易找出，既然關系確定了，然后通過遞推公式很容易寫出遞歸代碼。
2//?f(n-1)?為我前邊的人所在的當前層
3//?+?1?是層與層之間的計算關系
4f(n)?=?f(n-1)?+?1
▉ 總結：
我將以上一類遞歸問題命名為「遞歸計算型」的「層層計算類型」。
▉ 舉一反三：
求年齡的問題也是層層計算類型的問題，自己嘗試分析一下（一定要自己嘗試的去想，動手編碼，才能進一步領悟到遞歸技巧）。
問題一：有 5 個人坐在一起，問第 5 個人多少歲，他說比第 4 個人大 2 歲。問第 4 個人多少歲，他說比第 3 個人大2歲。問第 3 人多少歲，他說比第 2個 人大 2 歲。問第2個人多少歲，他說比第 1 個人大 2 歲。最后問第 1 個人，他說他是 10 歲。編寫程序，當輸入第幾個人時求出其對應的年齡。
問題二：單鏈表從尾到頭一次輸出結點值，用遞歸實現。
2、并列計算
并列計算，顧名思義，問題的解決方式是通過遞歸的并列計算來得到結果的。層與層之間并沒有一定的計算關系，而只是簡單的改變輸入的參數值。
▉ 例子：
最經典的題型就是斐波那契數列。觀察這樣一組數據0、 1、1、2、3、5、8、13、21、34...，去除第一個和第二個數據外，其余的數據等于前兩個數據之和（如：2 = 1 + 1，8 = 3 + 5，34 = 21 + 13）。你可以嘗試著根據「滿足遞歸的三個條件」以及「怎么寫出遞歸代碼」的步驟自己動手動腦親自分析一下。
我也在這里稍微做一個分析。
1）第一步：首先判斷能不能將問題分解為多個子問題，上邊我也分析過了，除了第一個和第二個數據，其他數據是前兩個數據之和。那么前兩個數據怎么知道呢？同樣的解決方式，是他們前兩個數之和。
2）第二步：找到終止條件，如果不斷的找到前兩個數之和，直到最前邊三個數據 0、1、1 。如果遞歸求第一個 1 時，前邊的數據不夠，所以這也是我們找到的終止條件。
3）第三步：既然我們終止條件和關系找到了，遞推公式也就不難寫出 f(n) = f(n-1) + f(n-2)（n 為要求的第幾個數字的值）。
4）轉化為遞歸代碼如下：
2????//?終止條件
3????if(n?==?0)?return?0;
4????if(n?==?1)?return?1;
5????//?遞推公式
6????return?f(n-1)?+?f(n-2);
7}
▉ 總結：
我將上方的問題總結為并列計算型。也可以歸屬為層層計算的一種，只不過是 + 1 改成了加一個 f 函數自身的遞歸（說白了，遞歸的結果也是一個確切的數值）。
之所謂并列計算 f(n-1) 和 f(n-2) 互不打擾，各自遞歸計算各的值。最后我們將其計算的結果值相加是我們最想要的結果。
▉ 舉一反三：
問題：一只青蛙一次可以跳上 1 級臺階，也可以跳上2 級。求該青蛙跳上一個n 級的臺階總共有多少種跳法。
※ 分類二：遞歸枚舉型
遞歸枚舉型最多的應用就是回溯算法，枚舉出所有可能的情況，怎么枚舉所有情況呢？通過遞歸編程技巧進行枚舉。那什么是回溯算法？比如走迷宮，從入口走到出口，如果遇到死胡同，需要回退，退回上一個路口，然后走另一岔路口，重復上述方式，直到找到出口。
回溯算法最經典的問題又深度優先遍歷、八皇后問題等，應用非常廣泛，下邊以八皇后問題為例子，展開分析，其他利用遞歸枚舉型的回溯算法就很簡單了。
八皇后問題
在 8 X 8 的網格中，放入八個皇后（棋子），滿足的條件是，任意兩個皇后（棋子）都不能處于同一行、同一列或同一斜線上，問有多少種擺放方式？
圖（1）正確情況
圖（2）錯誤情況
▉ 問題分析：
要想滿足任意兩個皇后（棋子）都不能處于同一行、同一列或同一斜線上，需要一一枚舉皇后（棋子）的所有擺放情況，然后設定條件，篩選出滿足條件的情況。
▉ 算法思路：
我們把問題分析清楚了之后，怎么通過遞歸實現回溯算法枚舉八個皇后（棋子）出現的所有情況呢？
1）我們在 8 X 8 的網格中，先將第一枚皇后（棋子）擺放到第一行的第一列的位置（也就是坐標: (0,0)）。
2）然后我們在第二行安置第二個皇后（棋子），先放到第一列的位置，然后判斷同一行、同一列、同一斜線是否存在另一個皇后？如果存在，則該位置不合適，然后放到下一列的位置，然后在判斷是否滿足我們設定的條件。
3）第二個皇后（棋子）找到合適的位置之后，然后在第三行放置第三枚棋子，依次將八個皇后放到合適的位置。
4）這只是一種可能，因為我設定的第一個皇后是固定位置的，在網格坐標的（0,0） 位置，那么怎么枚舉所有的情況呢？然后我們不斷的改變第一個皇后位置，第二個皇后位置...... ，就可以枚舉出所有的情況。如果你和我一樣，看了這個題之后，如果還有點懵懵懂懂，那么直接分析代碼吧。
▉ 代碼實現：
雖然是用 javascript 實現的代碼，相信學過編程的小伙伴基本的代碼邏輯都可以看懂。根據上方總結的遞歸分析滿足的三個條件以及怎么寫出遞歸代碼的步驟，一步步來分析八皇后問題。
1、將問題分解為多個子問題
在上述的代碼分析和算法思路分析中，我們可以大體知道怎么分解該問題了，枚舉出八個皇后（棋子）所有的滿足情況可以分解為，先尋找每一種滿足的情況這種子問題。比如，每個子問題的算法思路就是上方列出的四個步驟。
2、找出終止條件
當遍歷到第八行的時候，遞歸結束。
2if(row?===?8){
3????//?打印第?n?種滿足的情況
4????console.log(result)
5????n++;
6????return;
7}
3、寫出遞推公式
isOkCulomn() 函數判斷找到的該位置是否滿足條件（不能處于同一行、同一列或同一斜線上）。如果滿足條件，我們返回 true，進入 if 判斷，row行數加一傳入進行遞歸下一行的皇后位置。直至遞歸遇到終止條件位置，column ++，將第一行的皇后放到下一位置，進行繼續遞歸，枚舉出所有可能的擺放情況。
2for(let?column?=?0;?column?<?8;?column++){
3????//?判斷當前的列位置是否合適
4????if(isOkCulomn(row,column)){
5????????//?保存皇后的位置
6????????result[row]?=?column;
7????????//?對下一行尋找數據
8????????cal8queens(row?+?1);
9????}
10????//?此循環結束后,繼續遍歷下一種情況,就會形成一種枚舉所有可能性
11}
2const?isOkCulomn?=?(row,column)?=>{
3????//?左上角列的位置
4????let?leftcolumn?=?column?-?1;
5????//?右上角列的位置
6????let?rightcolumn?=?column?+?1;
7
8????for(let?i?=?row?-?1;i?>=?0;?i--){
9????????//?判斷當前格子正上方是否有重復
10????????if(result[i]?===?column)?return?false;
11
12????????//?判斷當前格子左上角是否有重復
13????????if(leftcolumn?>=?0){
14????????????if(result[i]?===?leftcolumn)?return?false;
15????????}
16
17????????//?判斷當前格式右上角是否有重復
18????????if(leftcolumn?<?8){
19????????????if(result[i]?===?rightcolumn)?return?false;
20????????}
21
22????????//?繼續遍歷
23????????leftcolumn?--;
24????????rightcolumn?++;
25????}
26????return?true;
27}
4、轉換為遞歸代碼
2//?result?為數組，下標為行，數組中存儲的是每一行中皇后的存儲的列的位置。
3//?row?行??
4//?column?列
5//?n?計數滿足條件的多少種
6var?result?=?[];
7let?n?=?0
8const?cal8queens?=?(row)?=>{
9????//?終止條件
10????if(row?===?8){
11????????console.log(result)
12????????n++;
13????????return;
14????}
15????//?每一列的判斷
16????for(let?column?=?0;?column?<?8;?column++){
17????????//?判斷當前的列位置是否合適
18????????if(isOkCulomn(row,column)){
19????????????//?保存皇后的位置
20????????????result[row]?=?column;
21????????????//?對下一行尋找數據
22????????????cal8queens(row?+?1);
23????????}
24????????//?此循環結束后,繼續遍歷下一種情況,就會形成一種枚舉所有可能性
25????}
26}
27
28//?判斷當前列是否合適
29const?isOkCulomn?=?(row,column)?=>{
30????//?設置左上角
31????let?leftcolumn?=?column?-?1;
32????let?rightcolumn?=?column?+?1;
33
34????for(let?i?=?row?-?1;i?>=?0;?i--){
35????????//?判斷當前格子正上方是否有重復
36????????if(result[i]?===?column)?return?false;
37
38????????//?判斷當前格子左上角是否有重復
39????????if(leftcolumn?>=?0){
40????????????if(result[i]?===?leftcolumn)?return?false;
41????????}
42
43????????//?判斷當前格式右上角是否有重復
44????????if(leftcolumn?<?8){
45????????????if(result[i]?===?rightcolumn)?return?false;
46????????}
47
48????????//?繼續遍歷
49????????leftcolumn?--;
50????????rightcolumn?++;
51????}
52????return?true;
53}
54
55//?遞歸打印所有情況
56const?print?=?(result)=>{
57????for(let?i?=?0;i?<?8;?i++){
58????????for(let?j?=?0;j?<?8;?j++){
59????????????if(result[i]?===?j){
60????????????????console.log('Q'?+?'?')
61????????????}else{
62????????????????console.log('*'?+?'?')
63????????????}
64????????}
65????}
66}
67
68//?測試
69cal8queens(0);
70console.log(n)
▉ 總結
上述八皇后的問題就是用遞歸來枚舉所有情況，然后再從中設置條件，只篩選滿足條件的選項。上述代碼建議多看幾遍，親自動手實踐一下。一開始解決八皇后問題，我自己看了好長時間才明白的，以及遞歸如何發揮技巧作用的。
▉ 舉一反三：
如果你想練練手，可以自己實現以下圖的深度優先遍歷，這個理解起來并不難，可以自己動手嘗試著寫一寫，我把代碼傳到我的 Github 上了。
※ 分類三：遞歸選擇型
所謂的遞歸選擇型，每個子問題都要面臨選擇，求最優解的情況。有的小伙伴會說，求最優解動態規劃最適合，對的，沒錯，但是遞歸通過選擇型枚舉所有情況，設置條件，求得問題的最優解也是可以實現的，所有我呢將其這一類問題歸為遞歸選擇型問題。
0 -1 背包問題
0 - 1 背包問題，了解過的小伙伴也是很熟悉的了。其實這個問題也屬于回溯算法的一種，廢話不多說，直接上問題。有一個背包，背包總的承載重量是 Wkg。現在我們有 n 個物品，每個物品的重量不等，并且不可分割。我們現在期望選擇幾件物品，裝載到背包中。在不超過背包所能裝載重量的前提下，如何讓背包中物品的總重量最大？
▉ 問題分析：
如果你對該問題看懵了，沒關系，我們一點點的分析。假如每個物品我們有兩種狀態，總的裝法就有 2^n種，怎么才能不重復的窮舉這些可能呢？
▉ 算法思路：
我們可以把物品依次排列，整個問題就分解為了 n 個階段，每個階段對應一個物品怎么選擇。先對第一個物品進行處理，選擇裝進去或者不裝進去，然后再遞歸地處理剩下的物品。
▉ 代碼實現：
2var?max?=?Number.MIN_VALUE;
3//?i:?對第?i?個物品做出選擇
4//?currentw:?當前背包的總重量
5//?goods：數組，存儲每個物品的質量
6//?n:?物品的數量
7//?weight:?背包應承受的重量
8const?f?=?(i,?currentw,?goods,?n,?weight)?=>?{
9????//?終止條件
10????if(currentw?===?weight?||?i?===?n){
11????????if(currentw?>?max){
12????????????//?保存滿足條件的最大值
13????????????max?=?currentw;
14????????}
15????????return?;
16????}
17
18????//?選擇跳過當前物品不裝入背包
19????f(i+1,?currentw,?goods,?n,?weight)
20
21????//?將當前物品裝入背包
22????//?判斷當前物品裝入背包之前是否超過背包的重量,如果已經超過當前背包重量，就不要就繼續裝了
23????if(currentw?+?goods[i]?<=?weight){
24????????f(i+1?,currentw?+?goods[i],?goods,?n,?weight)
25????}
26}
27
28let?a?=?[2,2,4,6,3]
29f(0,0,a,5,10)
30console.log(max)
遞歸的缺點
雖然遞歸的使用非常的簡潔，但是也有很多缺點，也是我們在使用中需要額外注意的地方和優化的地方。
1、遞歸堆棧溢出
▉ 理解堆棧溢出
1）遞歸的本質就是重復調用本身的過程，本身是什么？當然是一個函數，那好，函數中有參數以及一些局部的聲明的變量，相信很多小伙伴只會用函數，而不知道函數中的變量是怎么存儲的吧。沒關系，等你聽我分析完，你就會了。
2）函數中變量是存儲到系統中的棧中的，棧數據結構的特點就是先進后出，后進先出。一個函數中的變量的使用情況就是隨函數的聲明周期變化的。當我們執行一個函數時，該函數的變量就會一直不斷的壓入棧中，當函數執行完畢銷毀的時候，棧內的元素依次出棧。還是不懂，沒關系，看下方示意圖。
3）我們理解了上述過程之后，回到遞歸上來，我們的遞歸調用是在函數里調用自身，且當前函數并沒有銷毀，因為當前函數在執行自身層層遞歸進去了，所以遞歸的過程，函數中的變量一直不斷的壓棧，由于我們系統棧或虛擬機棧空間是非常小的，當棧壓滿之后，再壓時，就會導致堆棧溢出。
2function?f(n){
3????var?a?=?1;
4????var?b?=?2;
5????return?a?+?b;
6}
▉ 解決辦法
那么遇到這種情況，我們怎么解決呢？
通常我們設置遞歸深度，簡單的理解就是，如果遞歸超過我們設置的深度，我們就退出，不再遞歸下去。還是那排隊打飯的例子，如下：
2let?depth?=?0;
3
4function?f(n){
5????depth++；
6????//?如果超過遞歸深度，拋出錯誤
7????if(depth?>?1000)?throw?'error';
8????//?終止條件
9????if(n?==?1)?retun?1;
10????//?遞推公式
11????return?f(n-1)?+?1;
12}
2、遞歸重復元素
有些遞歸問題中，存在重復計算問題，比如求斐波那契數列，我們畫一下遞歸樹如下圖，我們會發現有很多重復遞歸計算的值，重復計算會導致程序的時間復雜度很高，而且是指數級別的，導致我們的程序效率低下。
▉ 解決辦法
重復計算問題，我們應該怎么解決？有的小伙伴想到了，我們把已經計算過的值保存起來，每次遞歸計算之前先檢查一下保存的數據有沒有該數據，如果有，我們拿出來直接用。如果沒有，我們計算出來保存起來。一般我們用散列表來保存。（所謂的散列表就是鍵值對的形式，如 map ）
2let?map?=?new?Map();
3function?f(n)?{
4????//?終止條件
5????if(n?==?0)?return?0;
6????if(n?==?1)?return?1;
7
8????//?如果散列表中存在當前計算的值，就直接返回，不再進行遞歸計算
9????if(map.has(n)){
10????????return?map.get(n);
11?????}
12
13????//?遞推公式
14????let?num?=?f(n-1)?+?f(n-2);
15????//?將當前的值保存到散列表中
16????map.set(n,num)
17????return?num;
18}
3、遞歸高空間復雜度
因為遞歸時函數的變量的存儲需要額外的棧空間，當遞歸深度很深時，需要額外的內存占空間就會很多，所以遞歸有非常高的空間復雜度。
最后想說的話
最后可能說的比較打雞血，很多人一遇到遞歸就會崩潰掉，比如我，哈哈。無論以后遇到什么困難，不要對它們產生恐懼，而是當做一種挑戰，當你經過長時間的戰斗，突破層層困難，最后突破挑戰的時候，你會感激曾經的自己當初困難面前沒有放棄。
這一點我深有感觸，有時候對于難題感到很無助，雖然自己沒有在一所好的大學，沒有好的資源，更沒有人去專心的指導你，但是我一直相信這都是老天給我發出的挑戰書，我會繼續努力，寫出更多高質量的文章。
如果覺得不錯，可以給小鹿加個雞腿哦！再次感謝各位不離不棄，一起做一個不甘平凡的碼農！
本文原文共有 8000 字，小鹿總結了整整一個星期，本公眾號為縮減版，點擊 “閱讀原文” 查看完整版。
總結
以上是生活随笔為你收集整理的数据结构与算法之递归系列的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Python | 深入浅出字符串
- 下一篇： Python 2.7 将于7个月后终结，