你了解Python中的遞歸嗎

你了解Python中的遞歸嗎？很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。

專注于為中小企業(yè)提供成都做網(wǎng)站、網(wǎng)站制作服務(wù),電腦端+手機端+微信端的三站合一,更高效的管理,為中小企業(yè)遵義免費做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動了數(shù)千家企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網(wǎng)站建設(shè)實現(xiàn)規(guī)模擴充和轉(zhuǎn)變。

1. 遞歸概述

遞歸（ recursion）是一種編程技巧，某些情況下，甚至是無可替代的技巧。遞歸可以大幅簡化代碼，看起來非常簡潔，但遞歸設(shè)計卻非常抽象，不容易掌握。通常，我們都是自上而下的思考問題， 遞歸則是自下而上的解決問題——這就是遞歸看起來不夠直觀的原因。那么，究竟什么是遞歸呢？讓我們先從生活中找一個栗子。

我們都有在黑暗的放映廳里找座位的經(jīng)驗：問問前排的朋友坐的是第幾排，加上一，就是自己當前所處位置的排號。如果前排的朋友不知道自己是第幾排，他可以用同樣的方法得到自己的排號，然后再告訴你。如果前排的前排的朋友也不知道自己是第幾排，他就如法炮制。這樣的推導，不會無限制地進行下去，因為問到第一排的時候，坐在第一排的朋友一定會直接給出答案的。這就是遞歸算法在生活中的應(yīng)用實例。

關(guān)于遞歸，不太嚴謹?shù)亩x是“一個函數(shù)在運行時直接或間接地調(diào)用了自身”。嚴謹一點的話，一個遞歸函數(shù)必須滿足下面兩個條件：

（1）至少有一個明確的遞歸結(jié)束條件，我們稱之為遞歸出口，也有人喜歡把該條件叫做遞歸基。

（2）有向遞歸出口方向靠近的直接或間接的自身調(diào)用（也被稱作遞歸調(diào)用）。

遞歸雖然晦澀，亦有規(guī)律可循。掌握了基本的遞歸理論，才有可能將其應(yīng)用于復(fù)雜的算法設(shè)計中。

2. 線性遞歸

我們先從最經(jīng)典的兩個遞歸算法開始——階乘（factorial）和斐波那契數(shù)列（Fibonacci sequence）。幾乎所有討論遞歸算法的話題，都是從從它們開始的。階乘的概念比較簡單，唯一需要說明的是，0的階乘是1而非0。為此，我專門請教了我的女兒，她是數(shù)學專業(yè)的學生。斐波那契數(shù)列，又稱黃金分割數(shù)列，指的是這樣一個數(shù)列：1、1、2、3、5、8、13、21、34、……在數(shù)學上，斐波納契數(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)用

這兩個函數(shù)的結(jié)構(gòu)都非常簡單，遞歸出口和自身調(diào)用清晰明了，但二者有一個顯著的區(qū)別：階乘函數(shù)中，只用一次自身調(diào)用，而斐波那契函數(shù)則有兩次自身調(diào)用。

階乘遞歸函數(shù)每一層的遞歸對自身的調(diào)用只有一次，因此每一層次上至多只有一個實例，且它們構(gòu)成一個線性的次序關(guān)系。此類遞歸模式稱作“線性遞歸”，這是遞歸最基本形式。非線性遞歸（比如斐波那契遞歸函數(shù)）在每一層上都會產(chǎn)生兩個實例，時間復(fù)雜度為

，極易導致堆棧溢出。

其實，用循環(huán)的方法同樣可以簡潔地寫出上面兩個函數(shù)。的確，很多情況下，遞歸能夠解決的問題，循環(huán)也可以做到。但是，更多的情況下，循環(huán)是無法取代遞歸的。因此，深入研究遞歸理論是非常有必要的。

3. 尾遞歸

接下來，我們將上面的階乘遞歸函數(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() 的寫法，就會發(fā)現(xiàn)很有意思的問題。factorial_A() 的自身調(diào)用屬于表達式的一部分，這意味著自身調(diào)用不是函數(shù)的最后一步，而是拿到自身調(diào)用的結(jié)果后，需要再做一次乘法運算；factorial_B() 的自身調(diào)用則是函數(shù)的最后一步。像 factorial_B() 函數(shù)這樣，當自身調(diào)用是整個函數(shù)體中最后執(zhí)行的語句，且它的返回值不屬于表達式的一部分時，這個遞歸調(diào)用就是尾遞歸（Tail Recursion）。尾遞歸函數(shù)的特點是在回歸過程中不用做任何操作，這個特性很重要，因為大多數(shù)現(xiàn)代的編譯器會利用這種特點自動生成優(yōu)化的代碼。

分別使用 factorial_A() 和 factorial_B() 計算5的階乘，下圖所示的計算過程，清晰展示了尾遞歸的優(yōu)勢：不用花費大量的?？臻g來保存上次遞歸中的參數(shù)、局部變量等，這是因為上次遞歸操作結(jié)束后，已經(jīng)將之前的數(shù)據(jù)計算出來，傳遞給當前的遞歸函數(shù)，這樣上次遞歸中的局部變量和參數(shù)等就會被刪除，釋放空間，從而不會造成棧溢出。

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)勢，但這一類遞歸一般都可轉(zhuǎn)化為循環(huán)語句。

4. 單向遞歸

前文中兩個遞歸函數(shù)，不管是階乘還是斐波那契數(shù)列，遞歸總是向著遞歸出口方向進行，沒有分支，沒有反復(fù)，這樣的遞歸，我們稱之為單向遞歸。在文件遞歸遍歷等應(yīng)用場合，搜索完一個文件夾，通常要返回至父級目錄，繼續(xù)搜索其他兄弟文件夾，這個過程就不是單向的，而是有分叉的、帶回溯的。通常復(fù)雜遞歸都不是單向的，算法設(shè)計起來就比較困難。

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() 實現(xiàn)的基于循環(huán)的文件遍歷方法。雖然是循環(huán)結(jié)構(gòu)，如果不熟悉 walk() 的話，這個函數(shù)看起來還是很不直觀。我更喜歡下面的遞歸遍歷方法。

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)先處理本級文件夾中的子文件夾，遞歸向縱深發(fā)展；廣度優(yōu)先就是優(yōu)先處理本級文件夾中的文件，遞歸向水平方向發(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))

看完上述內(nèi)容是否對您有幫助呢？如果還想對相關(guān)知識有進一步的了解或閱讀更多相關(guān)文章，請關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝您對創(chuàng)新互聯(lián)的支持。

網(wǎng)頁名稱：你了解Python中的遞歸嗎
網(wǎng)址分享：http://muchs.cn/article28/johdcp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供響應(yīng)式網(wǎng)站、虛擬主機、網(wǎng)站收錄、網(wǎng)站建設(shè)、網(wǎng)站制作、域名注冊

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)