如何更好地理解遞歸算法？Python實(shí)例詳解

遞歸是一種較為抽象的數(shù)學(xué)邏輯，可以簡單的理解為「程序調(diào)用自身的算法」。

維基百科對遞歸的解釋是：

遞歸（英語：Recursion），又譯為遞回，在數(shù)學(xué)與計(jì)算機(jī)科學(xué)中，是指在函數(shù)的定義中使用函數(shù)自身的方法。遞歸一詞還較常用于描述以自相似方法重復(fù)事物的過程。

例如，當(dāng)兩面鏡子相互之間近似平行時，鏡中嵌套的圖像是以無限遞歸的形式出現(xiàn)的。也可以理解為自我復(fù)制的過程。

"遞"是傳遞的意思，"歸"是歸還的意思，先把一個方法一層層傳遞下去，然后傳遞到最后一層再把結(jié)果歸還回來。

比方說我排隊(duì)做核酸檢測，前面有100個人，我想問下醫(yī)務(wù)人員幾點(diǎn)下班，于是問了我前面那兄弟，他又問了他前面的人，一個個傳遞下去，最終傳遞到了醫(yī)務(wù)人員那里，回話說下午六點(diǎn)下班。這句話又往回傳，最終到了我這里，我知道了醫(yī)務(wù)人員六點(diǎn)下班。

這個過程就是一個遞歸過程，如果說"傳話"本身是一種方法，那這整個傳話過程就是在調(diào)用自身方法，最終獲得了結(jié)果。

這和循環(huán)不一樣，循環(huán)相當(dāng)于給所有人都所有人都戴了耳機(jī)，然后有"中介"挨個去問你知道醫(yī)務(wù)人員幾點(diǎn)下班嗎，等問到醫(yī)務(wù)人員的時候，得到答案，“中介”告訴我六點(diǎn)下班。

實(shí)質(zhì)上，遞歸就是把一個大問題不斷拆解，像剝洋蔥一樣，最終拆解到最小層面，會返回解題結(jié)果。

用Python舉一個最簡單的遞歸函數(shù)例子，講一講什么是遞歸的應(yīng)用。

我們經(jīng)常會看到函數(shù)會調(diào)用自身來實(shí)現(xiàn)循環(huán)操作，比如求階乘的函數(shù)。

整數(shù)n的階乘即

如下面5行Python代碼，就能實(shí)現(xiàn)階乘的計(jì)算

輸出：120

很多人可能困惑這里面的計(jì)算邏輯，為什么fact函數(shù)中調(diào)用了自身，最終能得到結(jié)果。

我們可以按照數(shù)學(xué)邏輯進(jìn)行推演：

整數(shù)n的階乘是：

整數(shù)n-1的階乘是：

所以可以推斷

這里是不是一種 fact方法可以為每個數(shù)所調(diào)用，最終調(diào)用到了n=1的時候，就返回結(jié)果n的階乘。

大家看上圖，遞歸函數(shù)會一層層往下調(diào)用，最終到n=1的時候，往上返回結(jié)果。

這就是遞歸的全過程，如果我們給遞歸下一個準(zhǔn)確的定義，可以概括為以下3點(diǎn)：

1、至少有一個明確的遞歸結(jié)束條件；

2、給出遞歸終止時的處理辦法；

3、每次進(jìn)入更深一層遞歸時，問題規(guī)模(計(jì)算量)相比上次遞歸都應(yīng)有所減少

以上面代碼為例：

除了常見的階乘案例，還有斐波那契數(shù)列，也是遞歸的經(jīng)典用法。

斐波那契數(shù)列：

這個數(shù)列從第3項(xiàng)開始，每一項(xiàng)都等于前兩項(xiàng)之和。

它以如下被以遞推的方法定義：

在Python中，我們可以使用遞歸函數(shù)的方式去實(shí)現(xiàn)斐波那契數(shù)列：

使用數(shù)學(xué)方法進(jìn)行推導(dǎo)：

fab(0) = 0（初始值）

fab(1) = 1（初始值）

對所有大于1的整數(shù)n：fab(n) = fab(n-1)+ fab(n-2)（遞歸定義）

其實(shí)以上兩個遞歸的案例都可以用數(shù)學(xué)歸納法來解釋，就是高中數(shù)學(xué)的知識。

一般地，證明一個與自然數(shù)n有關(guān)的命題P(n），有如下步驟：

（1）證明當(dāng)n取第一個值n0時命題成立。n0對于一般數(shù)列取值為0或1，但也有特殊情況；

（2）假設(shè)當(dāng)n=k（k≥n0，k為自然數(shù)）時命題成立，證明當(dāng)n=k+1時命題也成立。

綜合（1）（2），對一切自然數(shù)n（≥n0），命題P(n）都成立。

除了數(shù)學(xué)的解釋，之前也看到有人對遞歸更加形象的解釋：

1、我們已經(jīng)完成了嗎？如果完成了，返回結(jié)果。如果沒有這樣的終止條件，遞歸將會永遠(yuǎn)地繼續(xù)下去。

2、如果沒有，則簡化問題，解決較容易的問題，并將結(jié)果組裝成原始問題的解決辦法。然后返回該解決辦法。

哈哈,到這里大家是不是對遞歸有了一個更加深刻的認(rèn)識。

如果還不清楚，沒關(guān)系，這里還有更多的遞歸案例，用Python來實(shí)現(xiàn)，可以說非常簡潔。

「最大公因數(shù)：」

「從 1 到 n 的數(shù)字之和：」

「字符串倒序：」

「漢諾塔問題：」

「二分法找有序列表指定值：」

有位大佬說過：To Iterate is Human, to Recurse, Divine.

中文譯為：人理解迭代，神理解遞歸。

可見遞歸是非常神奇的算法，它的神奇之處在于它允許用戶用有限的語句描述無限的對象。

當(dāng)然人無完人，遞歸也是有缺點(diǎn)的，它一般效率較低，且會導(dǎo)致調(diào)用棧溢出。

因?yàn)檫f歸不斷調(diào)用自身函數(shù)，且產(chǎn)生大量變量，而?？臻g的容量是有限的，循環(huán)太多就會效率低下，甚至導(dǎo)致調(diào)用棧溢出

加入知識星球【我們談?wù)摂?shù)據(jù)科學(xué)】

500+小伙伴一起學(xué)習(xí)！

關(guān)鍵詞： 如何更好地理解遞歸算法Python實(shí)例詳解 python