建站
咨詢(xún)
售后
建站咨詢(xún)
新聞中心
1. 遞歸概述
遞歸（ recursion）是一種編程技巧，某些情況下，甚至是無(wú)可替代的技巧。遞歸可以大幅簡(jiǎn)化代碼，看起來(lái)非常簡(jiǎn)潔，但遞歸設(shè)計(jì)卻非常抽象，不容易掌握。通常，我們都是自上而下的思考問(wèn)題， 遞歸則是自下而上的解決問(wèn)題——這就是遞歸看起來(lái)不夠直觀的原因。那么，究竟什么是遞歸呢？讓我們先從生活中找一個(gè)栗子。
我們都有在黑暗的放映廳里找座位的經(jīng)驗(yàn)：?jiǎn)枂?wèn)前排的朋友坐的是第幾排，加上一，就是自己當(dāng)前所處位置的排號(hào)。如果前排的朋友不知道自己是第幾排，他可以用同樣的方法得到自己的排號(hào)，然后再告訴你。如果前排的前排的朋友也不知道自己是第幾排，他就如法炮制。這樣的推導(dǎo)，不會(huì)制地進(jìn)行下去，因?yàn)閱?wèn)到第一排的時(shí)候，坐在第一排的朋友一定會(huì)直接給出答案的。這就是遞歸算法在生活中的應(yīng)用實(shí)例。
關(guān)于遞歸，不太嚴(yán)謹(jǐn)?shù)亩x是“一個(gè)函數(shù)在運(yùn)行時(shí)直接或間接地調(diào)用了自身”。嚴(yán)謹(jǐn)一點(diǎn)的話(huà)，一個(gè)遞歸函數(shù)必須滿(mǎn)足下面兩個(gè)條件：
（1）至少有一個(gè)明確的遞歸結(jié)束條件，我們稱(chēng)之為遞歸出口，也有人喜歡把該條件叫做遞歸基。
（2）有向遞歸出口方向靠近的直接或間接的自身調(diào)用（也被稱(chēng)作遞歸調(diào)用）。
遞歸雖然晦澀，亦有規(guī)律可循。掌握了基本的遞歸理論，才有可能將其應(yīng)用于復(fù)雜的算法設(shè)計(jì)中。
2. 線(xiàn)性遞歸
我們先從最經(jīng)典的兩個(gè)遞歸算法開(kāi)始——階乘（factorial）和斐波那契數(shù)列（Fibonacci sequence）。幾乎所有討論遞歸算法的話(huà)題，都是從從它們開(kāi)始的。階乘的概念比較簡(jiǎn)單，唯一需要說(shuō)明的是，0的階乘是1而非0。為此，我專(zhuān)門(mén)請(qǐng)教了我的女兒，她是數(shù)學(xué)專(zhuān)業(yè)的學(xué)生。斐波那契數(shù)列，又稱(chēng)黃金分割數(shù)列，指的是這樣一個(gè)數(shù)列：1、1、2、3、5、8、13、21、34、……在數(shù)學(xué)上，斐波納契數(shù)列是這樣定義的：
F(0)=1，F(xiàn)(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N，N為正整數(shù)集）
階乘和斐波那契數(shù)列的遞歸算法如下：
def factorial(n): if n == 0: # 遞歸出口 return 1 return n*factorial(n-1) # 向遞歸出口方向靠近的自身調(diào)用 def fibonacci(n): if n < 2: # 遞歸出口 return 1 return fibonacci(n-1) + fibonacci(n-2) # 向遞歸出口方向靠近的自身調(diào)用
這兩個(gè)函數(shù)的結(jié)構(gòu)都非常簡(jiǎn)單，遞歸出口和自身調(diào)用清晰明了，但二者有一個(gè)顯著的區(qū)別：階乘函數(shù)中，只用一次自身調(diào)用，而斐波那契函數(shù)則有兩次自身調(diào)用。
階乘遞歸函數(shù)每一層的遞歸對(duì)自身的調(diào)用只有一次，因此每一層次上至多只有一個(gè)實(shí)例，且它們構(gòu)成一個(gè)線(xiàn)性的次序關(guān)系。此類(lèi)遞歸模式稱(chēng)作“線(xiàn)性遞歸”，這是遞歸最基本形式。非線(xiàn)性遞歸（比如斐波那契遞歸函數(shù)）在每一層上都會(huì)產(chǎn)生兩個(gè)實(shí)例，時(shí)間復(fù)雜度為
，極易導(dǎo)致堆棧溢出。
其實(shí)，用循環(huán)的方法同樣可以簡(jiǎn)潔地寫(xiě)出上面兩個(gè)函數(shù)。的確，很多情況下，遞歸能夠解決的問(wèn)題，循環(huán)也可以做到。但是，更多的情況下，循環(huán)是無(wú)法取代遞歸的。因此，深入研究遞歸理論是非常有必要的。
3. 尾遞歸
接下來(lái)，我們將上面的階乘遞歸函數(shù)改造一下，仍然用遞歸的方式實(shí)現(xiàn)。為了便于比較，我們把兩種算法放在一起。
def factorial_A(n): if n == 0: # 遞歸出口 return 1 return n*factorial_A(n-1) # 向遞歸出口方向靠近的自身調(diào)用 def factorial_B(n, k=1): if n == 0: # 遞歸出口 return k k *= n n -= 1 return factorial_B(n,k) # 向遞歸出口方向靠近的自身調(diào)用
比較 factorial_A() 和 factorial_B() 的寫(xiě)法，就會(huì)發(fā)現(xiàn)很有意思的問(wèn)題。factorial_A() 的自身調(diào)用屬于表達(dá)式的一部分，這意味著自身調(diào)用不是函數(shù)的最后一步，而是拿到自身調(diào)用的結(jié)果后，需要再做一次乘法運(yùn)算；factorial_B() 的自身調(diào)用則是函數(shù)的最后一步。像 factorial_B() 函數(shù)這樣，當(dāng)自身調(diào)用是整個(gè)函數(shù)體中最后執(zhí)行的語(yǔ)句，且它的返回值不屬于表達(dá)式的一部分時(shí)，這個(gè)遞歸調(diào)用就是尾遞歸（Tail Recursion）。尾遞歸函數(shù)的特點(diǎn)是在回歸過(guò)程中不用做任何操作，這個(gè)特性很重要，因?yàn)榇蠖鄶?shù)現(xiàn)代的編譯器會(huì)利用這種特點(diǎn)自動(dòng)生成優(yōu)化的代碼。
分別使用 factorial_A() 和 factorial_B() 計(jì)算5的階乘，下圖所示的計(jì)算過(guò)程，清晰展示了尾遞歸的優(yōu)勢(shì)：不用花費(fèi)大量的?？臻g來(lái)保存上次遞歸中的參數(shù)、局部變量等，這是因?yàn)樯洗芜f歸操作結(jié)束后，已經(jīng)將之前的數(shù)據(jù)計(jì)算出來(lái)，傳遞給當(dāng)前的遞歸函數(shù)，這樣上次遞歸中的局部變量和參數(shù)等就會(huì)被刪除，釋放空間，從而不會(huì)造成棧溢出。
factorial_A(5) 5 * factorial_A(4) 5 * 4 * factorial_A(3) 5 * 4 * 3 * factorial_A(2) 5 * 4 * 3 * 2 * factorial_A(1) 5 * 4 * 3 * 2 * 1 * factorial_A(0) 5 * 4 * 3 * 2 * 1 5 * 4 * 3 * 2 5 * 4 * 6 5 * 24 120 factorial_B(5, k=1) factorial_B(4, k=5) factorial_B(3, k=20) factorial_B(2, k=60) factorial_B(1, k=120) factorial_B(0, k=120) 120
尾遞歸雖然有低耗高效的優(yōu)勢(shì)，但這一類(lèi)遞歸一般都可轉(zhuǎn)化為循環(huán)語(yǔ)句。
4. 單向遞歸
前文中兩個(gè)遞歸函數(shù)，不管是階乘還是斐波那契數(shù)列，遞歸總是向著遞歸出口方向進(jìn)行，沒(méi)有分支，沒(méi)有反復(fù)，這樣的遞歸，我們稱(chēng)之為單向遞歸。在文件遞歸遍歷等應(yīng)用場(chǎng)合，搜索完一個(gè)文件夾，通常要返回至父級(jí)目錄，繼續(xù)搜索其他兄弟文件夾，這個(gè)過(guò)程就不是單向的，而是有分叉的、帶回溯的。通常復(fù)雜遞歸都不是單向的，算法設(shè)計(jì)起來(lái)就比較困難。
import os def ergodic(folder): for root, dirs, files in os.walk(folder): for dir_name in dirs: print(os.path.join(root, dir_name)) for file_name in files: print(os.path.join(root, file_name))
上面是借助于 os 模塊的 walk() 實(shí)現(xiàn)的基于循環(huán)的文件遍歷方法。雖然是循環(huán)結(jié)構(gòu)，如果不熟悉 walk() 的話(huà)，這個(gè)函數(shù)看起來(lái)還是很不直觀。我更喜歡下面的遞歸遍歷方法。
import os def ergodic(folder): for item in os.listdir(folder): obj = os.path.join(folder, item) print(obj) if os.path.isdir(obj): ergodic(obj)
5. 深度優(yōu)先與廣度優(yōu)先
遍歷文件通常有兩種策略：深度優(yōu)先搜索 DFS（depth-first search） 和廣度優(yōu)先搜索BFS（breadth-first search） 。顧名思義，深度優(yōu)先就是優(yōu)先處理本級(jí)文件夾中的子文件夾，遞歸向縱深發(fā)展；廣度優(yōu)先就是優(yōu)先處理本級(jí)文件夾中的文件，遞歸向水平方向發(fā)展。
import os def ergodic_DFS(folder): """基于深度優(yōu)先的文件遍歷""" dirs, files = list(), list() for item in os.listdir(folder): if os.path.isdir(os.path.join(folder, item)): dirs.append(item) else: files.append(item) for dir_name in dirs: ergodic(os.path.join(folder, dir_name)) for file_name in files print(os.path.join(folder, file_name)) def ergodic_BFS(folder): """基于廣度優(yōu)先的文件遍歷""" dirs, files = list(), list() for item in os.listdir(folder): if os.path.isdir(os.path.join(folder, item)): dirs.append(item) else: files.append(item) for file_name in files print(os.path.join(folder, file_name)) for dir_name in dirs: ergodic(os.path.join(folder, dir_name))
python學(xué)習(xí)網(wǎng)，免費(fèi)的在線(xiàn)學(xué)習(xí)python平臺(tái)，歡迎關(guān)注！
本文名稱(chēng)：創(chuàng)新互聯(lián)Python教程：一文了解Python中的遞歸
網(wǎng)頁(yè)URL：http://www.dlmjj.cn/article/dppiooj.html
