python 利用棧和隊(duì)列模擬遞歸的過(guò)程
一、遞歸
遞歸調(diào)用:一個(gè)函數(shù),調(diào)用的自身,稱(chēng)為遞歸調(diào)用
遞歸函數(shù):一個(gè)可以調(diào)用自身的函數(shù)稱(chēng)為遞歸函數(shù)
凡是循環(huán)能干的事,遞歸都能干
方法:
1、寫(xiě)出臨界條件
2、找這一次和上一次的關(guān)系
3、假設(shè)當(dāng)前函數(shù)已經(jīng)能用,調(diào)用自身計(jì)算上一次的結(jié)果再求出本次的結(jié)果
下面我們通過(guò)兩段代碼簡(jiǎn)單看一下遞歸和非遞歸的區(qū)別:
輸入一個(gè)大于等于1的數(shù),求1到n的和!
# 普通函數(shù)方法 def hanshu(n): sum = 0 # 循環(huán)遍歷每一個(gè)數(shù)字,將他們加到一個(gè)事先定義好的變量上,直到加完 for x in range(1, n+1): sum += x return sum
下面看一下通過(guò)遞歸的方法:
# 遞歸 def digui(n): if n == 1: return 1 # 如果n等于1證明已經(jīng)遞歸到最后,返回1,這就是上述的臨界條件 else: return n + digui(n-1) # 當(dāng)沒(méi)有達(dá)到臨界條件時(shí),用n加上對(duì)n-1的遞歸,每次都把n加進(jìn)去,但是后面依然是使用當(dāng)下這個(gè)遞歸函數(shù),會(huì)再次調(diào)用計(jì)算n-1,直到遞歸結(jié)束,也就是將從n到1的數(shù)全部遞歸完
在實(shí)際應(yīng)用中,遞歸是十分消耗內(nèi)存的,但是有些事情他很容易去做,很容易理解。下面,就通過(guò)一個(gè)案例介紹一下遞歸的用法。
二、遞歸遍歷目錄
下面的內(nèi)容我就通過(guò)解釋代碼來(lái)講解了,如果哪里講的不清楚,歡迎大家下方評(píng)論提意見(jiàn)。
import os # 由于我們遍歷目錄,所以要找到那個(gè)目錄并操作,os模塊包含普遍的操作系統(tǒng)功能 path = "" # 這是我們要遍歷的目錄的路徑,需要自己寫(xiě)進(jìn)去 # 既然是遞歸函數(shù),那么肯定要有個(gè)函數(shù),而且這個(gè)函數(shù)還將在函數(shù)內(nèi)部再次被調(diào)用 def getAllDir(path, sp = ''): # 參數(shù)中傳入路徑和sp,這個(gè)我最后說(shuō)一句你就明白了 # 得到當(dāng)前目錄下的所有文件 filesList = os.listdir(path) # os.listdir()是os模塊下的一個(gè)方法,相當(dāng)于Linux中的ls,查看所有文件 sp += " " # 這個(gè)也先放一下 # 處理每一個(gè)文件 for fileName in filesList: # 遍歷剛才找到的目錄下的所有文件 # 判斷是否是目錄(要用絕對(duì)路徑) fileAbsPath = os.path.join(path,fileName) # join是os模塊下將兩個(gè)路徑拼接在一起的意思,第二個(gè)參數(shù)不能有斜杠。因?yàn)槲覀円袛嘁幌逻@個(gè)文件是一個(gè)普通文件還是一個(gè)目錄,所有要先把他的絕對(duì)路徑整理出來(lái) if os.path.isdir(fileAbsPath): # isdir是判斷是否為目錄,是則返回True print(sp + "目錄:", fileName) # 打印當(dāng)前這個(gè)文件,他是個(gè)目錄 getAllDir(fileAbsPath,sp = " ") # 這里就開(kāi)始遞歸了,因?yàn)槲覀円业秸麄€(gè)目錄里的東西,所以當(dāng)這個(gè)文件還是個(gè)目錄的時(shí)候我們需要繼續(xù)向下找 else: print(sp + "普通文件:", fileName) # 如果僅僅是個(gè)普通文件,那么他里面也就沒(méi)有其他文件了,就可以直接打印他了 getAllDir(path) # 這里是調(diào)用函數(shù),讓遍歷開(kāi)始 # 最后我來(lái)說(shuō)一下開(kāi)始寫(xiě)的那個(gè)sp,是space的意思,有人也許現(xiàn)在就明白了。那個(gè)其實(shí)就是讓我們方便觀察,因?yàn)槊看未蛴《际琼斝袑?xiě)的,我們分不清他的目錄結(jié)構(gòu),所以通過(guò)空格來(lái)調(diào)整。在函數(shù)內(nèi)部寫(xiě)一個(gè)空格增加的表達(dá)式,可以使調(diào)用次數(shù)和空格數(shù)相關(guān)起來(lái),遞歸的越深,證明目錄的級(jí)越低,那么空格越多
三、棧模擬遞歸遍歷目錄(深度遍歷)
# 整體思路是沒(méi)有變得,這里沒(méi)有寫(xiě)到的也許是重復(fù)的,看下上面注釋就好了 # 寫(xiě)了一半想起來(lái)應(yīng)該回來(lái)寫(xiě)一下棧:棧就是一個(gè)容器,但它只有一個(gè)口,入棧出棧都從這一個(gè)口,而且這個(gè)棧很細(xì),進(jìn)去了就不能顛倒位置了,所以,每入棧一個(gè)元素他在最外面時(shí)候可以出來(lái),否則得等前面的走完了它才可以出來(lái) import os def getAllDirDFS(path): stack = [] # 這里是用棧來(lái)模擬,我們先創(chuàng)建一個(gè)列表當(dāng)做棧 stack.append(path) # 首先,先向棧里壓入路徑 # 處理?xiàng)#?dāng)棧為空時(shí)結(jié)束循環(huán)(棧為空就說(shuō)明棧里沒(méi)有普通文件和目錄了,因?yàn)槲覀兪敲坎僮饕粋€(gè)要把那個(gè)取出來(lái)) while len(stack) != 0: # 從棧中取出數(shù)據(jù) dirPath = stack.pop() # pop函數(shù)是刪除最后一個(gè)元素,同時(shí)還有一個(gè)返回值,就是去除的那個(gè)元素,我們?cè)俳邮找幌碌鹊扔? # 目錄下所有文件 filesList = os.listdir(dirPath) # 這個(gè)和上面一樣 # 處理每一個(gè)文件,如果是普通文件則打印出來(lái),如果是目錄則將該目錄地址壓棧 for fileName in filesList: # print(dirPath) fileAbsPath = os.path.join(dirPath,fileName) # print(fileAbsPath) if os.path.isdir(fileAbsPath): # 是目錄就壓棧 print("目錄:" + fileName) stack.append(fileAbsPath) # 當(dāng)是目錄時(shí)入棧,它這時(shí)就在最外面,下一次循環(huán)時(shí)候要取出棧的元素是不是還是這個(gè)啊,既然是它的話(huà)就還有找他內(nèi)部的東西,等把他找完了才繼續(xù)找和他并列的那些文件。就是說(shuō)抓住一根繩子使勁往下找,找到頭沒(méi)有了才返回來(lái),這就是深度優(yōu)先遍歷 else: # 打印普通文件 print("普通:" + fileName) getAllDirDFS(path)
四、隊(duì)列模擬遞歸遍歷目錄(廣度遍歷)
# 這回記住了,先說(shuō)一下隊(duì)列,隊(duì)是一個(gè)兩端開(kāi)口的模型,一頭進(jìn)一頭出,當(dāng)然還有雙向隊(duì)列,循環(huán)等等,我們就簡(jiǎn)單用一下最基本的隊(duì)列 import collections # 隊(duì)列在python的包里有,所以我們直接調(diào)用一下,不用以為這個(gè)很難,他也只不過(guò)是類(lèi)型是queue,實(shí)際的思想是一樣的,入隊(duì)append,因?yàn)檫@個(gè)是在右側(cè),也就是后方入隊(duì),另一邊出的話(huà)就是popleft,左側(cè)出,是不是很通俗,只是改了一下出來(lái)的口 def getAllDirBFS(path): queue = collections.deque() # 創(chuàng)建一個(gè)隊(duì)列,只要記得后面用法就是上面我說(shuō)的那個(gè)不同就可以了 queue.append(path) while len(queue) != 0: dirPath = queue.popleft() # 僅僅這里不同,因?yàn)殛?duì)列模擬是另一端出隊(duì) 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) # 大家想一下,棧是哪里進(jìn)哪里出,也就是,剛進(jìn)去的元素,接下來(lái)的一次循環(huán)又出來(lái)了,那便是一條路走到頭,是深度遍歷;那么現(xiàn)在一頭進(jìn)另一頭出是什么意思呢,就是即便判斷了這個(gè)是一個(gè)目錄,但我現(xiàn)在不執(zhí)行你,我要把你前面這些都查一遍,找完是目錄的都添加在后面,之后再遍歷你們這些,就是把一層的內(nèi)容找完再找下一層,被稱(chēng)為廣度優(yōu)先遍歷。
總結(jié)
以上所述是小編給大家介紹的python 利用棧和隊(duì)列模擬遞歸的過(guò)程,希望對(duì)大家有所幫助,如果大家有任何疑問(wèn)請(qǐng)給我留言,小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)腳本之家網(wǎng)站的支持!
- python實(shí)現(xiàn)堆棧與隊(duì)列的方法
- 棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)的基本概念及其相關(guān)的Python實(shí)現(xiàn)
- Python基于list的append和pop方法實(shí)現(xiàn)堆棧與隊(duì)列功能示例
- Python編程實(shí)現(xiàn)雙鏈表,棧,隊(duì)列及二叉樹(shù)的方法示例
- Python數(shù)據(jù)結(jié)構(gòu)之棧、隊(duì)列的實(shí)現(xiàn)代碼分享
- Python基于列表模擬堆棧和隊(duì)列功能示例
- Python常見(jiàn)數(shù)據(jù)結(jié)構(gòu)之棧與隊(duì)列用法示例
- Python中棧、隊(duì)列與優(yōu)先級(jí)隊(duì)列的實(shí)現(xiàn)方法
- Python實(shí)現(xiàn)的棧、隊(duì)列、文件目錄遍歷操作示例
- Python數(shù)據(jù)結(jié)構(gòu)之棧、隊(duì)列及二叉樹(shù)定義與用法淺析
- Python 實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)中的的棧隊(duì)列
- Python實(shí)現(xiàn)棧和隊(duì)列的簡(jiǎn)單操作方法示例
相關(guān)文章
如何使用 Python 中的功能和庫(kù)創(chuàng)建 n-gram
在計(jì)算語(yǔ)言學(xué)中,n-gram 對(duì)于語(yǔ)言處理、上下文和語(yǔ)義分析非常重要,它們是從令牌字符串中相鄰的連續(xù)單詞序列,本文將討論如何使用 Python 中的功能和庫(kù)創(chuàng)建 n-gram,感興趣的朋友一起看看吧2023-09-09Python Opencv任意形狀目標(biāo)檢測(cè)并繪制框圖
這篇文章主要為大家詳細(xì)介紹了Python Opencv任意形狀目標(biāo)檢測(cè),并繪制框圖,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2019-07-07Django中使用 Closure Table 儲(chǔ)存無(wú)限分級(jí)數(shù)據(jù)
對(duì)于數(shù)據(jù)量大的情況(比如用戶(hù)之間有邀請(qǐng)鏈,有點(diǎn)三級(jí)分銷(xiāo)的意思),就要用到 closure table 的結(jié)構(gòu)來(lái)進(jìn)行存儲(chǔ)。這篇文章主要介紹了Django中使用 Closure Table 儲(chǔ)存無(wú)限分級(jí)數(shù)據(jù),需要的朋友可以參考下2019-06-06Python實(shí)現(xiàn)自動(dòng)運(yùn)行代碼的方法詳解
在軟件開(kāi)發(fā)和數(shù)據(jù)科學(xué)領(lǐng)域,自動(dòng)運(yùn)行代碼是提高效率和確保一致性的關(guān)鍵,本文將深入探討如何使用Python實(shí)現(xiàn)自動(dòng)運(yùn)行代碼的各種方法,希望對(duì)大家有所幫助2023-12-12Python利用Nagios增加微信報(bào)警通知的功能
Nagios是一款開(kāi)源的免費(fèi)網(wǎng)絡(luò)監(jiān)視工具,能有效監(jiān)控Windows、Linux和Unix的主機(jī)狀態(tài),交換機(jī)路由器等網(wǎng)絡(luò)設(shè)置,打印機(jī)等,本文給大家介紹Python利用Nagios增加微信報(bào)警通知的功能,需要的朋友參考下2016-02-02Python 刪除連續(xù)出現(xiàn)的指定字符的實(shí)例
今天小編就為大家分享一篇Python 刪除連續(xù)出現(xiàn)的指定字符的實(shí)例,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2018-06-06python數(shù)據(jù)分析Numpy庫(kù)的常用操作
numpy 是 Python 的一個(gè)科學(xué)計(jì)算的庫(kù),提供了矩陣運(yùn)算的功能,其一般與 Scipy、matplotlib 一起使用,這篇文章總結(jié)下python數(shù)據(jù)分析Numpy庫(kù)的常用操作,感興趣的朋友一起看看吧2022-01-01openCV中值濾波和均值濾波的代碼實(shí)現(xiàn)
在我們生活中的有很多時(shí)候都可以用到濾波,例如美顏的磨皮功能,本文就詳細(xì)的介紹了openCV中值濾波和均值濾波的代碼實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-03-03Python?matplotlib繪制散點(diǎn)圖配置(萬(wàn)能模板案例)
這篇文章主要介紹了Python?matplotlib繪制散點(diǎn)圖配置(萬(wàn)能模板案例),散點(diǎn)圖是指在??回歸分析???中,數(shù)據(jù)點(diǎn)在直角坐標(biāo)系平面上的?分布圖???,散點(diǎn)圖表示因變量隨??自變量???而?變化???的大致趨勢(shì),據(jù)此可以選擇合適的函數(shù)??對(duì)數(shù)???據(jù)點(diǎn)進(jìn)行?擬合2022-07-07