摘要：終止條件遞推公式遞歸的分類(lèi)通過(guò)做大量的題，根據(jù)遞歸解決不同的問(wèn)題，引申出來(lái)的幾種解決和思考的方式。我們通過(guò)層與層之間的計(jì)算關(guān)系用遞推公式表達(dá)出來(lái)做計(jì)算，經(jīng)過(guò)層層的遞歸，最終得到結(jié)果值。

幾個(gè)月之前就想寫(xiě)這樣一篇文章分享給大家，由于自己有心而力不足，沒(méi)有把真正的學(xué)到的東西沉淀下來(lái)，所以一直在不斷的自學(xué)?？赡苁且?yàn)樵谝凰鞔髮W(xué)，資源也比較少，只能自己在網(wǎng)搜索相關(guān)資料，在互聯(lián)網(wǎng)上遇到了一些朋友的幫助下去深入理解，然后自己抽出大量時(shí)間做題總結(jié)、歸納，才會(huì)把已有的知識(shí)概念所被自己吸收和理解，形成了自己的技術(shù)思想體系。

然后自己又用了一個(gè)星期的時(shí)間去整理、分類(lèi)，才有了這篇 8000 字有關(guān)遞歸知識(shí)的分享，希望能夠幫助正在學(xué)習(xí)遞歸的小伙伴們。而且有了這篇文章的支撐和動(dòng)力，往后還會(huì)寫(xiě)出關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法一些難懂的概念簡(jiǎn)單化。如果文章中有錯(cuò)誤的地方，希望大家指正，能夠?yàn)樗朔窒沓龈匈|(zhì)量的內(nèi)容！

看了很多關(guān)于遞歸的文章，也總結(jié)了很多遞歸的文章，也看了多篇文章下方讀者的評(píng)論。有的讀者評(píng)論到文章清晰易懂，有的卻噴作者寫(xiě)的存在很多錯(cuò)誤，埋怨作者寫(xiě)出來(lái)很垃圾，還不如不寫(xiě)。我想從理性的角度說(shuō)一下，創(chuàng)作者寫(xiě)文章的最初好意是能夠幫助別人對(duì)此知識(shí)點(diǎn)有進(jìn)一步的了解，并不代表一定能夠滿足每個(gè)人的要求。

另一方面，每篇文章的作者可能理解的不夠透徹，很多地方可能存在許多錯(cuò)誤，包括理解上的錯(cuò)誤，筆誤等，這也是寫(xiě)文章的第二個(gè)目的，能夠讓別人挑出自己文章中的不足，能夠達(dá)到與別人共同進(jìn)步的目的，一舉兩得，兩全其美。

接下來(lái)分享的文章是關(guān)于遞歸的，這篇文章不單單分享遞歸的一切，我覺(jué)得更重要的是向每位讀者傳遞一個(gè)思想。思想？對(duì)的，沒(méi)錯(cuò)！這篇文章不能說(shuō)包含遞歸的邊邊角角，但是通過(guò)自己的理論上的學(xué)習(xí)和實(shí)踐，有了自己的一套遞歸思想。

什么問(wèn)題該用遞歸，什么問(wèn)題用遞歸簡(jiǎn)潔，什么問(wèn)題就不能使用遞歸解決，以及對(duì)于特定的問(wèn)題用遞歸解決的陷阱，能不能進(jìn)一步對(duì)遞歸進(jìn)行二次優(yōu)化，這些都是今天小鹿分享的內(nèi)容。

遞歸，顧名思義，有遞有歸才叫遞歸，有遞無(wú)歸，有歸無(wú)遞那叫 “耍流氓” 。

我們學(xué)習(xí)一門(mén)技術(shù)也好，編程語(yǔ)言也好，首先學(xué)習(xí)之前我們知道它將能給我們帶來(lái)什么，能幫助我們解決什么樣的問(wèn)題，這也是激勵(lì)我們?nèi)W(xué)習(xí)它的動(dòng)力所在。

從數(shù)組到鏈表、散列表，再到基本算法等，直到遇到遞歸之后，感覺(jué)非常的難理解。我相信每個(gè)人都有這種感覺(jué)，一開(kāi)始覺(jué)得非常難，經(jīng)歷了九九八十一難之后，還是沒(méi)有弄懂遞歸里邊的貓膩，然后就自然而然的跳過(guò)了。

后來(lái)我就開(kāi)始刷了一個(gè)月的 LeetCode 題，發(fā)現(xiàn)遞歸在數(shù)據(jù)結(jié)構(gòu)與算法中有著一席之地，統(tǒng)治著江山。大部分的題都可以用遞歸去解決，如：二叉樹(shù)的遍歷、回溯算法、0-1 背包問(wèn)題、深度優(yōu)先遍歷、回溯算法等等，我整理了至少二三十到關(guān)于遞歸的題，才發(fā)現(xiàn)遞歸的重要性，所以不得不重新深入遞歸學(xué)習(xí)，所有有了今天這篇文章。

上方我對(duì)遞歸“耍流氓”式的定義并不能讓你準(zhǔn)確的理解遞歸是什么，那么我們就來(lái)活生生的舉個(gè)生活中的例子。

比如你和小鹿我一樣，在大學(xué)里喜歡插隊(duì)打飯（作為一個(gè)三好學(xué)生，我怎么能干這種事呢？哈哈），那么隊(duì)伍后邊的同學(xué)本數(shù)著自己前邊還有 5 個(gè)同學(xué)就改輪到自己了，由于前邊同學(xué)不斷的插隊(duì)，這時(shí)他發(fā)現(xiàn)，怎么覺(jué)得自己離著打飯的窗口越來(lái)越遠(yuǎn)呢？這時(shí)如果他想知道自己在隊(duì)隊(duì)列中的的第幾個(gè)（前提是前邊不再有人插隊(duì)），用遞歸思想來(lái)解決，我們?cè)趺醋瞿兀?/p> 2、“遞”

于是他問(wèn)前邊的同學(xué)是第幾位，前邊的同學(xué)也不只到呀，于是前邊的同學(xué)問(wèn)他前邊的同學(xué)是第幾位，直到前邊第二個(gè)同學(xué)問(wèn)到第一個(gè)正在打飯的同學(xué)是隊(duì)伍的第幾個(gè)（有點(diǎn)小尷尬）。打飯的同學(xué)不耐煩的說(shuō)，沒(méi)看到我是第一個(gè)正在打飯嗎？這個(gè)過(guò)程其實(shí)是就是一個(gè)遞歸中“遞”的過(guò)程。

然后前邊打飯的第二個(gè)同學(xué)不耐煩的又告訴第三個(gè)同學(xué)，我是第二個(gè)，沒(méi)看單我前邊有個(gè)家伙正在打飯嗎？然后第三個(gè)傳給第四個(gè)，以后往后傳，直到那位逐漸遠(yuǎn)離窗口的同學(xué)的前一個(gè)人告訴他是第幾個(gè)之后，他知道了自己目前在隊(duì)伍中的第幾個(gè)位置。這個(gè)過(guò)程我們可以理解為遞歸中“歸”的過(guò)程。

“打飯的同學(xué)不耐煩的說(shuō)，沒(méi)看到我是第一個(gè)正在打飯嗎？”，在遞歸中，我們稱為終止條件。

1）問(wèn)題雖然是層層遞歸的分析，但是用程序表示的時(shí)候，不要層層的在大腦中調(diào)用遞歸代碼去想，這樣可能會(huì)使你完全陷入到 “遞” 的過(guò)程中去，“歸” 的時(shí)候，歸不出來(lái)了，這些都是我們交給計(jì)算機(jī)干的事情。
2）那我們?cè)趯?xiě)程序的時(shí)候怎么理解遞歸呢？我們只找問(wèn)題之間存在的關(guān)系，屏蔽掉遞歸的細(xì)節(jié)，具體看（五）分析。

通過(guò)上方的例子，我們可以很容易的總結(jié)出滿足遞歸的三個(gè)條件。

想知道自己在隊(duì)伍中的位置，將其問(wèn)題分解為“每個(gè)人所處隊(duì)伍中的位置”這樣的多個(gè)子問(wèn)題。

想要知道自己當(dāng)前的位置，就要問(wèn)前邊人所處的位置。那么前邊人想要知道自己所處的位置，就要知道他前邊人的位置。所以說(shuō)，該問(wèn)題和子問(wèn)題的解決思路相同，滿足第二個(gè)條件。

第一個(gè)正在打飯的同學(xué)說(shuō)自己是隊(duì)伍中的第一人，這就是所謂的終止條件，找到終止條件之后就開(kāi)始進(jìn)行“歸”的過(guò)程。

如果你對(duì)遞歸有了一定的了解，上邊的例子對(duì)你來(lái)說(shuō)小菜一碟，下邊還有更大的難度來(lái)進(jìn)行挑戰(zhàn)。那么問(wèn)題分析清楚了，怎么根據(jù)問(wèn)題編寫(xiě)出遞歸代碼來(lái)呢？

寫(xiě)遞歸公式最重要的一點(diǎn)就是找到該問(wèn)題和子問(wèn)題的關(guān)系，怎么找到之間存在的關(guān)系呢？這里我要強(qiáng)調(diào)注意的一點(diǎn)就是不要讓大腦試圖去想層層的遞歸過(guò)程，畢竟大腦的思考方式是順勢(shì)思考的（一開(kāi)始學(xué)習(xí)遞歸總是把自己繞繞進(jìn)去，歸的時(shí)候，就完全亂套的）。那怎么找到每個(gè)子問(wèn)題之間存在的某種關(guān)系呢？

我們只想其中一層（第一層關(guān)系），以上述為例，如果我想知道當(dāng)前隊(duì)伍的位置，所以我要之前前一個(gè)人的位置，然后 +1 就是我的位置了。對(duì)于他在什么位置，我絲毫不用關(guān)系，而是讓遞歸去解決他的位置。我們可以寫(xiě)出遞推公式如下：

// f(n) 代表當(dāng)前我在隊(duì)伍中的位置
// f(n-1) 代表我前邊那個(gè)人的位置
// 遞推公式
f(n) = f(n-1) + 1 

※ 注意：這個(gè)式子的含義就是 f(n) 求當(dāng)前 n 這個(gè)人的位置， f(n-1) + 1 代表的就是前一個(gè)人的位置 + 1 就是 n 的位置。

遞推公式我們很輕松的寫(xiě)出來(lái)了，但是沒(méi)有終止條件的遞推公式會(huì)永遠(yuǎn)的執(zhí)行下去的，所以我們要有一個(gè)終止條件終止程序的運(yùn)行。那么怎么找到終止條件呢？

所謂的終止條件就是已知的條件，比如上述的排隊(duì)打飯的例子中，第一個(gè)人正在窗口打飯，他的前邊是沒(méi)有人的，所以他是第一個(gè)。第一個(gè)人的位置為 1，我們應(yīng)該怎么表示呢？

// 終止條件
f(1) = 1;

※ 注意：有的問(wèn)題終止條件不止一個(gè)哦，比如：斐波那契數(shù)列。具體問(wèn)題具體分析。

遞推公式和終止條件我們分析出來(lái)了，那么將遞推公式轉(zhuǎn)化為遞歸代碼非常容易了。

function f(n){
    // 終止條件
    if(n == 1) retun 1;
    // 遞推公式
    return f(n-1) + 1;
}

通過(guò)做大量的題，根據(jù)遞歸解決不同的問(wèn)題，引申出來(lái)的幾種解決和思考的方式。之所以將其分類(lèi)，是為了能夠更好的理解遞歸在不同的問(wèn)題下起著什么作用，如：每層遞歸之間存在的關(guān)系、計(jì)算，以及遞歸枚舉所有情況和面臨選擇性問(wèn)題的遞歸。雖然分為了幾類(lèi)，但是遞歸的本質(zhì)是一成不變的。

將哪一類(lèi)用遞歸解決的問(wèn)題作為計(jì)算型呢？我簡(jiǎn)單總結(jié)了為兩點(diǎn)，層層計(jì)算和并列計(jì)算。

1、層層計(jì)算

層層計(jì)算，顧名思義，能夠用遞歸解決的問(wèn)題都可以分為多個(gè)子問(wèn)題，我們把每個(gè)子問(wèn)題可以抽象成一層，子問(wèn)題之間的關(guān)系可以表示為層與層之間的關(guān)系。我們通過(guò)層與層之間的計(jì)算關(guān)系用遞推公式表達(dá)出來(lái)做計(jì)算，經(jīng)過(guò)層層的遞歸，最終得到結(jié)果值。

▉ 例子：

我們?cè)倌巧戏脚抨?duì)打飯的例子來(lái)說(shuō)明，我們的子問(wèn)題已經(jīng)分析出來(lái)了，就是我想知道當(dāng)前在隊(duì)伍中的位置，就是去問(wèn)我前邊人的位置加一就是我當(dāng)前隊(duì)伍的位置，這為一層。而前邊這個(gè)人想知道當(dāng)前自己的位置，需要用同樣的解決思路，作為另一層。

層與層之間的關(guān)系是什么（我當(dāng)前隊(duì)伍中的位置與前邊人的位置存在什么樣的關(guān)系）？這時(shí)你會(huì)說(shuō)，當(dāng)前是 +1。這個(gè)大部分人都很容易找出，既然關(guān)系確定了，然后通過(guò)遞推公式很容易寫(xiě)出遞歸代碼。

// f(n) 為我所在的當(dāng)前層
// f(n-1) 為我前邊的人所在的當(dāng)前層
// + 1 是層與層之間的計(jì)算關(guān)系
f(n) = f(n-1) + 1

▉ 總結(jié)：

我將以上一類(lèi)遞歸問(wèn)題命名為「遞歸計(jì)算型」的「層層計(jì)算類(lèi)型」。

▉ 舉一反三：

求年齡的問(wèn)題也是層層計(jì)算類(lèi)型的問(wèn)題，自己嘗試分析一下（一定要自己嘗試的去想，動(dòng)手編碼，才能進(jìn)一步領(lǐng)悟到遞歸技巧）。

問(wèn)題一：有 5 個(gè)人坐在一起，問(wèn)第 5 個(gè)人多少歲，他說(shuō)比第 4 個(gè)人大 2 歲。問(wèn)第 4 個(gè)人多少歲，他說(shuō)比第 3 個(gè)人大2歲。問(wèn)第 3 人多少歲，他說(shuō)比第 2個(gè) 人大 2 歲。問(wèn)第2個(gè)人多少歲，他說(shuō)比第 1 個(gè)人大 2 歲。最后問(wèn)第 1 個(gè)人，他說(shuō)他是 10 歲。編寫(xiě)程序，當(dāng)輸入第幾個(gè)人時(shí)求出其對(duì)應(yīng)的年齡。

問(wèn)題二：單鏈表從尾到頭一次輸出結(jié)點(diǎn)值，用遞歸實(shí)現(xiàn)。

2、并列計(jì)算

并列計(jì)算，顧名思義，問(wèn)題的解決方式是通過(guò)遞歸的并列計(jì)算來(lái)得到結(jié)果的。層與層之間并沒(méi)有一定的計(jì)算關(guān)系，而只是簡(jiǎn)單的改變輸入的參數(shù)值。

▉ 例子：

最經(jīng)典的題型就是斐波那契數(shù)列。觀察這樣一組數(shù)據(jù) 0、 1、1、2、3、5、8、13、21、34...，去除第一個(gè)和第二個(gè)數(shù)據(jù)外，其余的數(shù)據(jù)等于前兩個(gè)數(shù)據(jù)之和（如：2 = 1 + 1，8 = 3 + 5，34 = 21 + 13）。你可以嘗試著根據(jù)「滿足遞歸的三個(gè)條件」以及「怎么寫(xiě)出遞歸代碼」的步驟自己動(dòng)手動(dòng)腦親自分析一下。

我也在這里稍微做一個(gè)分析：
1）第一步：首先判斷能不能將問(wèn)題分解為多個(gè)子問(wèn)題，上邊我也分析過(guò)了，除了第一個(gè)和第二個(gè)數(shù)據(jù)，其他數(shù)據(jù)是前兩個(gè)數(shù)據(jù)之和。那么前兩個(gè)數(shù)據(jù)怎么知道呢？同樣的解決方式，是他們前兩個(gè)數(shù)之和。

2）第二步：找到終止條件，如果不斷的找到前兩個(gè)數(shù)之和，直到最前邊三個(gè)數(shù)據(jù) 0、1、1 。如果遞歸求第一個(gè) 1 時(shí)，前邊的數(shù)據(jù)不夠，所以這也是我們找到的終止條件。

3）第三步：既然我們終止條件和關(guān)系找到了，遞推公式也就不難寫(xiě)出 f(n) = f(n-1) + f(n-2)（n 為要求的第幾個(gè)數(shù)字的值）。

4）轉(zhuǎn)化為遞歸代碼如下：

function f(n) {
    // 終止條件
    if(n == 0) return 0;
    if(n == 1) return 1;
    // 遞推公式
    return f(n-1) + f(n-2);
}

▉ 總結(jié)：

我將上方的問(wèn)題總結(jié)為并列計(jì)算型。也可以歸屬為層層計(jì)算的一種，只不過(guò)是 + 1 改成了加一個(gè) f 函數(shù)自身的遞歸（說(shuō)白了，遞歸的結(jié)果也是一個(gè)確切的數(shù)值）。之所謂并列計(jì)算 f(n-1) 和 f(n-2) 互不打擾，各自遞歸計(jì)算各的值。最后我們將其計(jì)算的結(jié)果值相加是我們最想要的結(jié)果。

▉ 舉一反三：

青蛙跳臺(tái)階的問(wèn)題也是一種并列計(jì)算的一種，自己嘗試著根據(jù)上邊的思路分析一下，實(shí)踐出真知（一定要自己嘗試的去想，動(dòng)手編碼，才能進(jìn)一步領(lǐng)悟到遞歸技巧）。

問(wèn)題：
一只青蛙一次可以跳上 1 級(jí)臺(tái)階，也可以跳上2 級(jí)。求該青蛙跳上一個(gè)n 級(jí)的臺(tái)階總共有多少種跳法。

遞歸枚舉型最多的應(yīng)用就是回溯算法，枚舉出所有可能的情況，怎么枚舉所有情況呢？通過(guò)遞歸編程技巧進(jìn)行枚舉。那什么是回溯算法？比如走迷宮，從入口走到出口，如果遇到死胡同，需要回退，退回上一個(gè)路口，然后走另一岔路口，重復(fù)上述方式，直到找到出口。

回溯算法最經(jīng)典的問(wèn)題又深度優(yōu)先遍歷、八皇后問(wèn)題等，應(yīng)用非常廣泛，下邊以八皇后問(wèn)題為例子，展開(kāi)分析，其他利用遞歸枚舉型的回溯算法就很簡(jiǎn)單了。

八皇后問(wèn)題

在 8 X 8 的網(wǎng)格中，放入八個(gè)皇后（棋子），滿足的條件是，任意兩個(gè)皇后（棋子）都不能處于同一行、同一列或同一斜線上，問(wèn)有多少種擺放方式？

▉ 問(wèn)題分析：

要想滿足任意兩個(gè)皇后（棋子）都不能處于同一行、同一列或同一斜線上，需要一一枚舉皇后（棋子）的所有擺放情況，然后設(shè)定條件，篩選出滿足條件的情況。

▉ 算法思路：

我們把問(wèn)題分析清楚了之后，怎么通過(guò)遞歸實(shí)現(xiàn)回溯算法枚舉八個(gè)皇后（棋子）出現(xiàn)的所有情況呢？

1）我們?cè)?8 X 8 的網(wǎng)格中，先將第一枚皇后（棋子）擺放到第一行的第一列的位置（也就是坐標(biāo): (0,0)）。

2）然后我們?cè)诘诙邪仓玫诙€(gè)皇后（棋子），先放到第一列的位置，然后判斷同一行、同一列、同一斜線是否存在另一個(gè)皇后？如果存在，則該位置不合適，然后放到下一列的位置，然后在判斷是否滿足我們?cè)O(shè)定的條件。

3）第二個(gè)皇后（棋子）找到合適的位置之后，然后在第三行放置第三枚棋子，依次將八個(gè)皇后放到合適的位置。

4）這只是一種可能，因?yàn)槲以O(shè)定的第一個(gè)皇后是固定位置的，在網(wǎng)格坐標(biāo)的（0,0） 位置，那么怎么枚舉所有的情況呢？然后我們不斷的改變第一個(gè)皇后位置，第二個(gè)皇后位置...... ，就可以枚舉出所有的情況。如果你和我一樣，看了這個(gè)題之后，如果還有點(diǎn)懵懵懂懂，那么直接分析代碼吧。

▉ 代碼實(shí)現(xiàn)：

雖然是用 javascript 實(shí)現(xiàn)的代碼，相信學(xué)過(guò)編程的小伙伴基本的代碼邏輯都可以看懂。根據(jù)上方總結(jié)的遞歸分析滿足的三個(gè)條件以及怎么寫(xiě)出遞歸代碼的步驟，一步步來(lái)分析八皇后問(wèn)題。

1、將問(wèn)題分解為多個(gè)子問(wèn)題

在上述的代碼分析和算法思路分析中，我們可以大體知道怎么分解該問(wèn)題了，枚舉出八個(gè)皇后（棋子）所有的滿足情況可以分解為，先尋找每一種滿足的情況這種子問(wèn)題。比如，每個(gè)子問(wèn)題的算法思路就是上方列出的四個(gè)步驟。

2、找出終止條件

當(dāng)遍歷到第八行的時(shí)候，遞歸結(jié)束。

// 終止條件
if(row === 8){
    // 打印第 n 種滿足的情況
    console.log(result)
    n++;
    return;
}

3、寫(xiě)出遞推公式

isOkCulomn() 函數(shù)判斷找到的該位置是否滿足條件（不能處于同一行、同一列或同一斜線上）。如果滿足條件，我們返回 true，進(jìn)入 if 判斷，row 行數(shù)加一傳入進(jìn)行遞歸下一行的皇后位置。直至遞歸遇到終止條件位置，column ++，將第一行的皇后放到下一位置，進(jìn)行繼續(xù)遞歸，枚舉出所有可能的擺放情況。

// 每一列的判斷
for(let column = 0; column < 8; column++){
    // 判斷當(dāng)前的列位置是否合適
    if(isOkCulomn(row,column)){
        // 保存皇后的位置
        result[row] = column;
        // 對(duì)下一行尋找數(shù)據(jù)
        cal8queens(row + 1);
    }
    // 此循環(huán)結(jié)束后,繼續(xù)遍歷下一種情況,就會(huì)形成一種枚舉所有可能性
}

// 判斷當(dāng)前列是否合適
const isOkCulomn = (row,column) =>{
    // 左上角列的位置
    let leftcolumn = column - 1;
    // 右上角列的位置
    let rightcolumn = column + 1;

    for(let i = row - 1;i >= 0; i--){
        // 判斷當(dāng)前格子正上方是否有重復(fù)
        if(result[i] === column) return false;

        // 判斷當(dāng)前格子左上角是否有重復(fù)
        if(leftcolumn >= 0){
            if(result[i] === leftcolumn) return false;
        }

        // 判斷當(dāng)前格式右上角是否有重復(fù)
        if(leftcolumn < 8){
            if(result[i] === rightcolumn) return false;
        }

        // 繼續(xù)遍歷
        leftcolumn --;
        rightcolumn ++;
    }
    return true;
}

4、轉(zhuǎn)換為遞歸代碼

// 變量
// result 為數(shù)組，下標(biāo)為行，數(shù)組中存儲(chǔ)的是每一行中皇后的存儲(chǔ)的列的位置。
// row 行  
// column 列
// n 計(jì)數(shù)滿足條件的多少種
var result = [];
let n = 0
const cal8queens = (row) =>{
    // 終止條件
    if(row === 8){
        console.log(result)
        n++;
        return;
    }
    // 每一列的判斷
    for(let column = 0; column < 8; column++){
        // 判斷當(dāng)前的列位置是否合適
        if(isOkCulomn(row,column)){
            // 保存皇后的位置
            result[row] = column;
            // 對(duì)下一行尋找數(shù)據(jù)
            cal8queens(row + 1);
        }
        // 此循環(huán)結(jié)束后,繼續(xù)遍歷下一種情況,就會(huì)形成一種枚舉所有可能性
    }
}

// 判斷當(dāng)前列是否合適
const isOkCulomn = (row,column) =>{
    // 設(shè)置左上角
    let leftcolumn = column - 1;
    let rightcolumn = column + 1;

    for(let i = row - 1;i >= 0; i--){
        // 判斷當(dāng)前格子正上方是否有重復(fù)
        if(result[i] === column) return false;

        // 判斷當(dāng)前格子左上角是否有重復(fù)
        if(leftcolumn >= 0){
            if(result[i] === leftcolumn) return false;
        }

        // 判斷當(dāng)前格式右上角是否有重復(fù)
        if(leftcolumn < 8){
            if(result[i] === rightcolumn) return false;
        }

        // 繼續(xù)遍歷
        leftcolumn --;
        rightcolumn ++;
    }
    return true;
}

// 遞歸打印所有情況
const print = (result)=>{
    for(let i = 0;i < 8; i++){
        for(let j = 0;j < 8; j++){
            if(result[i] === j){
                console.log("Q" + " ")
            }else{
                console.log("*" + " ")
            }
        }
    }
}

// 測(cè)試
cal8queens(0);
console.log(n)

▉ 總結(jié)

上述八皇后的問(wèn)題就是用遞歸來(lái)枚舉所有情況，然后再?gòu)闹性O(shè)置條件，只篩選滿足條件的選項(xiàng)。上述代碼建議多看幾遍，親自動(dòng)手實(shí)踐一下。一開(kāi)始解決八皇后問(wèn)題，我自己看了好長(zhǎng)時(shí)間才明白的，以及遞歸如何發(fā)揮技巧作用的。

▉ 舉一反三：

如果你想練練手，可以自己實(shí)現(xiàn)圖的深度優(yōu)先遍歷，這個(gè)理解起來(lái)并不難，可以自己動(dòng)手嘗試著寫(xiě)一寫(xiě)，我把代碼傳到我的 Github 上了。

所謂的遞歸選擇型，每個(gè)子問(wèn)題都要面臨選擇，求最優(yōu)解的情況。有的小伙伴會(huì)說(shuō)，求最優(yōu)解動(dòng)態(tài)規(guī)劃最適合，對(duì)的，沒(méi)錯(cuò)，但是遞歸通過(guò)選擇型「枚舉所有情況」，設(shè)置條件，求得問(wèn)題的最優(yōu)解也是可以實(shí)現(xiàn)的，所有我呢將其這一類(lèi)問(wèn)題歸為遞歸選擇型問(wèn)題，它也是一個(gè)回溯算法。

0 -1 背包問(wèn)題

0 - 1 背包問(wèn)題，了解過(guò)的小伙伴也是很熟悉的了。其實(shí)這個(gè)問(wèn)題也屬于回溯算法的一種，廢話不多說(shuō)，直接上問(wèn)題。有一個(gè)背包，背包總的承載重量是 Wkg?，F(xiàn)在我們有 n 個(gè)物品，每個(gè)物品的重量不等，并且不可分割。我們現(xiàn)在期望選擇幾件物品，裝載到背包中。在不超過(guò)背包所能裝載重量的前提下，如何讓背包中物品的總重量最大？

▉ 問(wèn)題分析：

如果你對(duì)該問(wèn)題看懵了，沒(méi)關(guān)系，我們一點(diǎn)點(diǎn)的分析。假如每個(gè)物品我們有兩種狀態(tài)，總的裝法就有 2^n 種，怎么才能不重復(fù)的窮舉這些可能呢？

▉ 算法思路：

我們可以把物品依次排列，整個(gè)問(wèn)題就分解為了 n 個(gè)階段，每個(gè)階段對(duì)應(yīng)一個(gè)物品怎么選擇。先對(duì)第一個(gè)物品進(jìn)行處理，選擇裝進(jìn)去或者不裝進(jìn)去，然后再遞歸地處理剩下的物品。

▉ 代碼實(shí)現(xiàn)：

這里有個(gè)技巧就是設(shè)置了條件，自動(dòng)篩選掉不滿足條件的情況，提高了程序的執(zhí)行效率。

// 用來(lái)存儲(chǔ)背包中承受的最大重量
var max = Number.MIN_VALUE;
// i: 對(duì)第 i 個(gè)物品做出選擇
// currentw: 當(dāng)前背包的總重量
// goods：數(shù)組，存儲(chǔ)每個(gè)物品的質(zhì)量
// n: 物品的數(shù)量
// weight: 背包應(yīng)承受的重量
const f = (i, currentw, goods, n, weight) => {
    // 終止條件
    if(currentw === weight || i === n){
        if(currentw > max){
            // 保存滿足條件的最大值
            max = currentw;
        }
        return ;
    }

    // 選擇跳過(guò)當(dāng)前物品不裝入背包
    f(i+1, currentw, goods, n, weight)

    // 將當(dāng)前物品裝入背包
    // 判斷當(dāng)前物品裝入背包之前是否超過(guò)背包的重量,如果已經(jīng)超過(guò)當(dāng)前背包重量，就不要就繼續(xù)裝了
    if(currentw + goods[i] <= weight){
        f(i+1 ,currentw + goods[i], goods, n, weight)
    }
}

let a = [2,2,4,6,3]
f(0,0,a,5,10)
console.log(max)

雖然遞歸的使用非常的簡(jiǎn)潔，但是也有很多缺點(diǎn)，也是我們?cè)谑褂弥行枰~外注意的地方和優(yōu)化的地方。

你可能會(huì)問(wèn)，遞歸和系統(tǒng)中的堆棧有什么關(guān)聯(lián)？不要急，聽(tīng)我慢慢細(xì)說(shuō)。

▉ 理解堆棧溢出

1）遞歸的本質(zhì)就是重復(fù)調(diào)用本身的過(guò)程，本身是什么？當(dāng)然是一個(gè)函數(shù)，那好，函數(shù)中有參數(shù)以及一些局部的聲明的變量，相信很多小伙伴只會(huì)用函數(shù)，而不知道函數(shù)中的變量是怎么存儲(chǔ)的吧。沒(méi)關(guān)系，等你聽(tīng)我分析完，你就會(huì)了。

2）函數(shù)中變量是存儲(chǔ)到系統(tǒng)中的棧中的，棧數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)就是先進(jìn)后出，后進(jìn)先出。一個(gè)函數(shù)中的變量的使用情況就是隨函數(shù)的聲明周期變化的。當(dāng)我們執(zhí)行一個(gè)函數(shù)時(shí)，該函數(shù)的變量就會(huì)一直不斷的壓入棧中，當(dāng)函數(shù)執(zhí)行完畢銷(xiāo)毀的時(shí)候，棧內(nèi)的元素依次出棧。還是不懂，沒(méi)關(guān)系，看下方示意圖。

3）我們理解了上述過(guò)程之后，回到遞歸上來(lái)，我們的遞歸調(diào)用是在函數(shù)里調(diào)用自身，且當(dāng)前函數(shù)并沒(méi)有銷(xiāo)毀，因?yàn)楫?dāng)前函數(shù)在執(zhí)行自身層層遞歸進(jìn)去了，所以遞歸的過(guò)程，函數(shù)中的變量一直不斷的壓棧，由于我們系統(tǒng)?；蛱摂M機(jī)棧空間是非常小的，當(dāng)棧壓滿之后，再壓時(shí)，就會(huì)導(dǎo)致堆棧溢出。

// 函數(shù)
function f(n){
    var a = 1;
    var b = 2;
    return a + b;
}

▉ 解決辦法

那么遇到這種情況，我們?cè)趺唇鉀Q呢？

通常我們?cè)O(shè)置遞歸深度，簡(jiǎn)單的理解就是，如果遞歸超過(guò)我們?cè)O(shè)置的深度，我們就退出，不再遞歸下去。還是那排隊(duì)打飯的例子，如下：

// 表示遞歸深度變量
let depth = 0;

function f(n){
    depth++；
    // 如果超過(guò)遞歸深度，拋出錯(cuò)誤
    if(depth > 1000) throw "error";
    // 終止條件
    if(n == 1) retun 1;
    // 遞推公式
    return f(n-1) + 1;
}

有些遞歸問(wèn)題中，存在重復(fù)計(jì)算問(wèn)題，比如求斐波那契數(shù)列，我們畫(huà)一下遞歸樹(shù)如下圖，我們會(huì)發(fā)現(xiàn)有很多重復(fù)遞歸計(jì)算的值，重復(fù)計(jì)算會(huì)導(dǎo)致程序的時(shí)間復(fù)雜度很高，而且是指數(shù)級(jí)別的，導(dǎo)致我們的程序效率低下。

如下圖遞歸樹(shù)中，求斐波那契數(shù)列 f(5) 的值，需要多次遞歸求 f(3) 和 f(2) 的值。

▉ 解決辦法

重復(fù)計(jì)算問(wèn)題，我們應(yīng)該怎么解決？有的小伙伴想到了，我們把已經(jīng)計(jì)算過(guò)的值保存起來(lái)，每次遞歸計(jì)算之前先檢查一下保存的數(shù)據(jù)有沒(méi)有該數(shù)據(jù)，如果有，我們拿出來(lái)直接用。如果沒(méi)有，我們計(jì)算出來(lái)保存起來(lái)。一般我們用散列表來(lái)保存。（所謂的散列表就是鍵值對(duì)的形式，如 map ）

// 斐波那契數(shù)列改進(jìn)后
let map = new Map();
function f(n) {
    // 終止條件
    if(n == 0) return 0;
    if(n == 1) return 1;
    
    // 如果散列表中存在當(dāng)前計(jì)算的值，就直接返回，不再進(jìn)行遞歸計(jì)算
    if(map.has(n)){
        return map.get(n);
     }
    
    // 遞推公式
    let num = f(n-1) + f(n-2);
    // 將當(dāng)前的值保存到散列表中
    map.set(n,num)
    return num;
}

因?yàn)檫f歸時(shí)函數(shù)的變量的存儲(chǔ)需要額外的?？臻g，當(dāng)遞歸深度很深時(shí)，需要額外的內(nèi)存占空間就會(huì)很多，所以遞歸有非常高的空間復(fù)雜度。

比如： f(n) = f(n-1)+1 ，空間復(fù)雜度并不是 O(1)，而是 O(n) 。

我們一起對(duì)遞歸做一個(gè)簡(jiǎn)單的總結(jié)吧，如果你還是沒(méi)有完全明白，沒(méi)關(guān)系，多看幾遍，說(shuō)實(shí)話，我這個(gè)人比較笨，前期看遞歸還不知道看了幾十遍才想明白，吃飯想，睡覺(jué)之前想，相信最后總會(huì)想明白的。

一個(gè)問(wèn)題能不能分解成多個(gè)子問(wèn)題來(lái)解決；

該問(wèn)題是否和子問(wèn)題的解決思路相同；

該問(wèn)題是否有終止條件。

尋找遞歸終止條件；

寫(xiě)出遞推公式；

轉(zhuǎn)化成遞歸代碼。

不要用大腦去想每一層遞歸的實(shí)現(xiàn)，記住這是計(jì)算機(jī)應(yīng)該做的事情，我們要做的就是弄懂遞歸之間的關(guān)系，從而屏蔽掉層層遞歸的細(xì)節(jié)。

遞歸警惕堆棧溢出

遞歸警惕重復(fù)計(jì)算

遞歸的高空間復(fù)雜度

最后可能說(shuō)的比較打雞血，很多人一遇到遞歸就會(huì)崩潰掉，比如我，哈哈。無(wú)論以后遇到什么困難，不要對(duì)它們產(chǎn)生恐懼，而是當(dāng)做一種挑戰(zhàn)，當(dāng)你經(jīng)過(guò)長(zhǎng)時(shí)間的戰(zhàn)斗，突破層層困難，最后突破挑戰(zhàn)的時(shí)候，你會(huì)感激曾經(jīng)的自己當(dāng)初困難面前沒(méi)有放棄。這一點(diǎn)我深有感觸，有時(shí)候?qū)τ陔y題感到很無(wú)助，雖然自己沒(méi)有在一所好的大學(xué)，沒(méi)有好的資源，更沒(méi)有人去專心的指導(dǎo)你，但是我一直相信這都是老天給我發(fā)出的挑戰(zhàn)書(shū)，我會(huì)繼續(xù)努力，寫(xiě)出更多高質(zhì)量的文章。

如果覺(jué)得本文對(duì)你有幫助，點(diǎn)個(gè)贊，我希望能夠讓更多處在遞歸困惑的人看到，謝謝各位支持！下一篇我打算出一篇完整關(guān)于鏈表的文章，終極目標(biāo)：將數(shù)據(jù)結(jié)構(gòu)與算法每個(gè)知識(shí)點(diǎn)寫(xiě)成一系列的文章。

作者：小鹿
座右銘：追求平淡不平凡，一生追求做一個(gè)不甘平凡的碼農(nóng)!
本文首發(fā)于 Github ，轉(zhuǎn)載請(qǐng)說(shuō)明出處：https://github.com/luxiangqiang/Blog/blob/master/articel/數(shù)據(jù)結(jié)構(gòu)與算法系列/數(shù)據(jù)結(jié)構(gòu)與算法之遞歸系列.md

個(gè)人公眾號(hào)：一個(gè)不甘平凡的碼農(nóng)。