這篇文章給大家介紹怎么在python中利用棧和隊列模擬遞歸，內(nèi)容非常詳細，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。
1、云計算，典型應用OpenStack。2、WEB前端開發(fā)，眾多大型網(wǎng)站均為Python開發(fā)。3.人工智能應用，基于大數(shù)據(jù)分析和深度學習而發(fā)展出來的人工智能本質(zhì)上已經(jīng)無法離開python。4、系統(tǒng)運維工程項目，自動化運維的標配就是python+Django/flask。5、金融理財分析，量化交易，金融分析。6、大數(shù)據(jù)分析。
一、遞歸
遞歸調(diào)用：一個函數(shù)，調(diào)用的自身，稱為遞歸調(diào)用
遞歸函數(shù)：一個可以調(diào)用自身的函數(shù)稱為遞歸函數(shù)
凡是循環(huán)能干的事，遞歸都能干
方法：
1、寫出臨界條件
2、找這一次和上一次的關系
3、假設當前函數(shù)已經(jīng)能用，調(diào)用自身計算上一次的結果再求出本次的結果
下面我們通過兩段代碼簡單看一下遞歸和非遞歸的區(qū)別：
輸入一個大于等于1的數(shù)，求1到n的和！
# 普通函數(shù)方法 def hanshu(n): sum = 0 # 循環(huán)遍歷每一個數(shù)字，將他們加到一個事先定義好的變量上，直到加完 for x in range(1, n+1): sum += x return sum
下面看一下通過遞歸的方法：
# 遞歸 def digui(n): if n == 1: return 1 # 如果n等于1證明已經(jīng)遞歸到最后，返回1，這就是上述的臨界條件 else: return n + digui(n-1) # 當沒有達到臨界條件時，用n加上對n-1的遞歸，每次都把n加進去，但是后面依然是使用當下這個遞歸函數(shù)，會再次調(diào)用計算n-1，直到遞歸結束，也就是將從n到1的數(shù)全部遞歸完
在實際應用中，遞歸是十分消耗內(nèi)存的，但是有些事情他很容易去做，很容易理解。下面，就通過一個案例介紹一下遞歸的用法。
二、遞歸遍歷目錄
下面的內(nèi)容我就通過解釋代碼來講解了，如果哪里講的不清楚，歡迎大家下方評論提意見。
import os # 由于我們遍歷目錄，所以要找到那個目錄并操作，os模塊包含普遍的操作系統(tǒng)功能 path = "" # 這是我們要遍歷的目錄的路徑，需要自己寫進去 # 既然是遞歸函數(shù)，那么肯定要有個函數(shù)，而且這個函數(shù)還將在函數(shù)內(nèi)部再次被調(diào)用 def getAllDir(path, sp = ''): # 參數(shù)中傳入路徑和sp，這個我最后說一句你就明白了 # 得到當前目錄下的所有文件 filesList = os.listdir(path) # os.listdir()是os模塊下的一個方法，相當于Linux中的ls，查看所有文件 sp += " " # 這個也先放一下 # 處理每一個文件 for fileName in filesList: # 遍歷剛才找到的目錄下的所有文件 # 判斷是否是目錄（要用絕對路徑） fileAbsPath = os.path.join(path,fileName) # join是os模塊下將兩個路徑拼接在一起的意思，第二個參數(shù)不能有斜杠。因為我們要判斷一下這個文件是一個普通文件還是一個目錄，所有要先把他的絕對路徑整理出來 if os.path.isdir(fileAbsPath): # isdir是判斷是否為目錄，是則返回True print(sp + "目錄：", fileName) # 打印當前這個文件，他是個目錄 getAllDir(fileAbsPath,sp = " ") # 這里就開始遞歸了，因為我們要找到整個目錄里的東西，所以當這個文件還是個目錄的時候我們需要繼續(xù)向下找 else: print(sp + "普通文件：", fileName) # 如果僅僅是個普通文件，那么他里面也就沒有其他文件了，就可以直接打印他了 getAllDir(path) # 這里是調(diào)用函數(shù)，讓遍歷開始 # 最后我來說一下開始寫的那個sp，是space的意思，有人也許現(xiàn)在就明白了。那個其實就是讓我們方便觀察，因為每次打印都是頂行寫的，我們分不清他的目錄結構，所以通過空格來調(diào)整。在函數(shù)內(nèi)部寫一個空格增加的表達式，可以使調(diào)用次數(shù)和空格數(shù)相關起來，遞歸的越深，證明目錄的級越低，那么空格越多
三、棧模擬遞歸遍歷目錄（深度遍歷）
重慶分公司
重慶分公司
# 整體思路是沒有變得，這里沒有寫到的也許是重復的，看下上面注釋就好了
# 寫了一半想起來應該回來寫一下棧：棧就是一個容器，但它只有一個口，入棧出棧都從這一個口，而且這個棧很細，進去了就不能顛倒位置了，所以，每入棧一個元素他在最外面時候可以出來，否則得等前面的走完了它才可以出來
import os
def getAllDirDFS(path):
stack = [] # 這里是用棧來模擬，我們先創(chuàng)建一個列表當做棧
stack.append(path) # 首先，先向棧里壓入路徑
# 處理棧，當棧為空時結束循環(huán)（棧為空就說明棧里沒有普通文件和目錄了，因為我們是每操作一個要把那個取出來）
while len(stack) != 0:
# 從棧中取出數(shù)據(jù)
dirPath = stack.pop() # pop函數(shù)是刪除最后一個元素，同時還有一個返回值，就是去除的那個元素，我們再接收一下等等用
# 目錄下所有文件
filesList = os.listdir(dirPath) # 這個和上面一樣
# 處理每一個文件，如果是普通文件則打印出來，如果是目錄則將該目錄地址壓棧
for fileName in filesList:
# print(dirPath)
fileAbsPath = os.path.join(dirPath,fileName)
# print(fileAbsPath)
if os.path.isdir(fileAbsPath):
# 是目錄就壓棧
print("目錄：" + fileName)
stack.append(fileAbsPath) # 當是目錄時入棧，它這時就在最外面，下一次循環(huán)時候要取出棧的元素是不是還是這個啊，既然是它的話就還有找他內(nèi)部的東西，等把他找完了才繼續(xù)找和他并列的那些文件。就是說抓住一根繩子使勁往下找，找到頭沒有了才返回來，這就是深度優(yōu)先遍歷
else:
# 打印普通文件
print("普通：" + fileName)
getAllDirDFS(path)四、隊列模擬遞歸遍歷目錄（廣度遍歷）
# 這回記住了，先說一下隊列，隊是一個兩端開口的模型，一頭進一頭出，當然還有雙向隊列，循環(huán)等等，我們就簡單用一下最基本的隊列
import collections # 隊列在python的包里有，所以我們直接調(diào)用一下，不用以為這個很難，他也只不過是類型是queue，實際的思想是一樣的，入隊append，因為這個是在右側，也就是后方入隊，另一邊出的話就是popleft，左側出，是不是很通俗，只是改了一下出來的口
def getAllDirBFS(path):
queue = collections.deque() # 創(chuàng)建一個隊列，只要記得后面用法就是上面我說的那個不同就可以了
queue.append(path)
while len(queue) != 0:
dirPath = queue.popleft() # 僅僅這里不同，因為隊列模擬是另一端出隊
filesList = os.listdir(dirPath)
for fileName in filesList:
fileAbsPath = os.path.join(dirPath,fileName)
if os.path.isdir(fileAbsPath):
print('目錄：' + fileName)
queue.append(fileAbsPath)
else:
print('文件：' + fileName)
getAllDirBFS(path)關于怎么在python中利用棧和隊列模擬遞歸就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。
另外有需要云服務器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。
