圖解！ACM 選手帶你玩轉遞迴演算法！

大家好呀，我是 Rocky0429。

今天來講一種很重要的演算法，全稱叫“遞上我心愛的小烏龜”，簡稱“

遞龜(歸)

”。

遞迴是演算法中的勞模，應用頻率很高。

你可以把它

理解成一種程式設計技巧

，它是實現很多其它高階演算法的基礎，像什麼二叉樹的遍歷，深度優先搜尋啥的都有它的身影。

所以遞迴一定要學好、吃飽，不然後面學習其它資料結構與演算法必然難上加難。

我儘量講懂，你一定要學會。

話不多說，正式開始。

什麼是遞迴？

老規矩，學習遞迴，首先要知道什麼是遞迴。

官方說法是：

直接呼叫自己或透過一系列呼叫語句間接地呼叫自己，叫做遞迴

。

是不是有點懵？

怎麼理解呢？舉個被舉爛的例子。

從前有座山，山裡有座廟，廟裡有個花和尚，花和尚在講故事，講的什麼故事呢？從前有座山，山裡有座廟，廟裡有個花和尚，花和尚在講故事，講的什麼故事呢？從前有座山，山裡有座廟，。。。。。

看懂了麼？在故事中重複提到了同樣的故事，這就是遞迴的核心性質。

說白了，

遞迴就是一種迴圈，一種自己呼叫自己的迴圈

。

如果你實在覺的想不明白，你就還把它理解成函式呼叫了一個與自己一模一樣的其它函式。

遞迴的條件

來寫個簡單的例子：

def

f

（

x

）：

return

x

+

f

（

x

-

1

）

當 x = 3 時，函式的運作是下面那樣：

不知道你發現了沒，這個可以一直寫下去，時間有多長，它可以寫多長。

這種和永動機一樣能幹的遞迴叫做

死迴圈

，在程式碼裡肯定不能這麼搞，遞迴遞迴，有遞還要有歸，只遞不歸，程式分分鐘崩給你看。

所以我們要

在遞迴里加個停止呼叫自己的條件，讓它跳出

。

def

f

（

x

）：

if

x

>

0

：

return

x

+

f

（

x

-

1

）

return

0

加了一個判斷條件後，當 x = 3 時：f（3） = 3 + f（2） = 3 + 2 + f（1） = 3 + 2 + 1 + f（0） = 3 + 2 + 1 + 0 = 6。

看懂了上面，其實

遞迴的條件

也呼之欲出了：

問題可以分解為多個重複的子問題（子問題僅存在資料規模的差距，比如　f(2) 和 f(1)）。

存在終止條件

。

如何寫遞迴程式碼？

編寫遞迴的程式碼，只要按照遞迴的條件去寫就好了。

即：

找出重複的子問題（遞推公式） + 終止條件

。

比如我們來算 n！。

我們都知道 n！ = 1 * 2 * 3 * 。。。 * n 且 0！ = 1。

當 n = 3 時，3！ = 3 * 2 * 1。

當 n = 4 時，4！ = 4 * 3 * 2 * 1。

很容易得出的遞推公式就是：

f

（

n

）

=

n

*

f

（

n

-

1

）

有了遞推公式，遞迴程式碼就成功了一半，剩下就是來看一下終止條件。

自然數最小的 0！ = 1，所以終止條件可以是 f（0） =1。

判斷是否只需要這一個終止條件，可以用較小的數測試測試一下，比如 n = 1 或者 n = 2。

PS

：“判斷終止條件的個數”這一步很重要，因為有時候需要兩個或者多個終止條件，比如我們很熟悉的斐波那契數列，後面實戰題碰到我會再講。

當 n = 1 時，f（1） = 1 * f（0），當 n = 2 時，f（2） = 2 * f（1），可以看出終止條件足夠。

所以程式碼成了：

def

f

（

n

）：

if

n

>

0

：

return

n

*

f

（

n

-

1

）

else

：

return

1

雖然這是個很簡單的題，但是也告訴了我們很多：涉及到遞迴問題，我們不要想太多，就是找出它的遞推公式和終止條件。

看起來很簡單，單單是找遞推公式的能力，就需要你理解它的性質，看穿它的本質，以及最勤奮的多加練習。

遞迴の坑

坑 1：棧溢位

我在之前的文章中講過棧這種後進先出的線性資料結構。在計算機中，當程式執行的時候，呼叫函式會佔用一片棧的記憶體空間，來儲存臨時變數。

當呼叫函式時，必然會將臨時變數壓入棧，等函式執行結束，這些臨時變量出棧。

如果是這樣的話，那你想如果遞迴的資料規模很大，這就會造成臨時變數一直在入棧，入到一定的地步，棧都被塞滿了，沒地方放了，就會造成

棧溢位錯誤

。

這個時候作業系統就會果斷出手，強行中斷程式。

那麼如何避免出現“棧溢位”這種錯誤呢？

可以人為設定遞迴呼叫的深度，遞迴超過這個深度就不再繼續，儘量保證程式不會崩掉。

棧是一種

後進先出

（Last in First Out）的資料結構，簡稱

LIFO

。

坑 2：重複計算

很多時候使用遞迴的時候會產生無謂的子操作。

比如我們都知道的斐波那契數列。

它的遞推公式是 f（n） = f（n-1） + f（n-2），我來把它簡單分解一下，如下圖。

上圖中的 f（2） 就被重複計算了，這還只是 n = 4 的情況，當 n 更大時，出現重複的會更多。

所以很多時候，用遞迴解決問題並不是最佳的，特別是有許多重複子問題的時候。

出現這種情況的解決辦法就是“

判重 + 記錄結果

”，就是

先儲存已經求解過的 f 值，然後每次新求一個 f 值的時候看下之前是否已經求解過該值，這樣就可以避免重複計算

。

到這的話，遞迴就全部講完了。

還是那句話，學習遞迴最重要的是學習它的演算法思想，這就需要理解它的性質，看穿它的本質，同時勤奮的多加練習。

相信臭寶們一定可以玩弄遞歸於股掌之中，學會了記得回來

點贊麼麼噠

～

我是 Rocky0429，我們下次見。

推薦閱讀：

保姆級教學！徹底學會時間複雜度和空間複雜度

蛋蛋慘遭陣列滑鐵盧，面試官建議回村養豬。

連結串列，畫幾下就整明白了！

呔！“棧”住，佇列！

ACM 選手帶你玩轉雜湊表！

ACM 選手帶你玩轉 KMP 演算法！