博客地址：http://www.cnblogs.com/yudanqu/ 一、遞歸 遞歸調用：一個函數，調用的自身，稱為遞歸調用 遞歸函數：一個可以調用自身的函數稱為遞歸函數 凡是迴圈能幹的事，遞歸都能幹 下麵我們通過兩段代碼簡單看一下遞歸和非遞歸的區別： 輸入一個大於等於1的數，求1到n的和！ 下 ...
博客地址：http://www.cnblogs.com/yudanqu/
一、遞歸
- 遞歸調用：一個函數，調用的自身，稱為遞歸調用
- 遞歸函數：一個可以調用自身的函數稱為遞歸函數
凡是迴圈能幹的事，遞歸都能幹
方法：
1、寫出臨界條件
2、找這一次和上一次的關係
3、假設當前函數已經能用，調用自身計算上一次的結果再求出本次的結果
下麵我們通過兩段代碼簡單看一下遞歸和非遞歸的區別：
輸入一個大於等於1的數，求1到n的和！
1 # 普通函數方法 2 3 def hanshu(n): 4 sum = 0 5 # 迴圈遍歷每一個數字，將他們加到一個事先定義好的變數上，直到加完 6 for x in range(1, n+1): 7 sum += x 8 return sum
下麵看一下通過遞歸的方法：
1 # 遞歸 2 3 def digui(n): 4 if n == 1: 5 return 1 # 如果n等於1證明已經遞歸到最後，返回1，這就是上述的臨界條件 6 else: 7 return n + digui(n-1) # 當沒有達到臨界條件時，用n加上對n-1的遞歸，每次都把n加進去，但是後面依然是使用當下這個遞歸函數，會再次調用計算n-1，直到遞歸結束，也就是將從n到1的數全部遞歸完
在實際應用中，遞歸是十分消耗記憶體的，但是有些事情他很容易去做，很容易理解。下麵，就通過一個案例介紹一下遞歸的用法。
二、遞歸遍歷目錄
下麵的內容我就通過解釋代碼來講解了，如果哪裡講的不清楚，歡迎大家下方評論提意見。
1 import os # 由於我們遍歷目錄，所以要找到那個目錄並操作，os模塊包含普遍的操作系統功能 2 3 path = "" # 這是我們要遍歷的目錄的路徑，需要自己寫進去 4 5 # 既然是遞歸函數，那麼肯定要有個函數，而且這個函數還將在函數內部再次被調用 6 def getAllDir(path, sp = ''): # 參數中傳入路徑和sp，這個我最後說一句你就明白了 7 # 得到當前目錄下的所有文件 8 filesList = os.listdir(path) # os.listdir()是os模塊下的一個方法，相當於Linux中的ls，查看所有文件 9 10 sp += " " # 這個也先放一下 11 # 處理每一個文件 12 for fileName in filesList: # 遍歷剛纔找到的目錄下的所有文件 13 # 判斷是否是目錄（要用絕對路徑） 14 fileAbsPath = os.path.join(path,fileName) # join是os模塊下將兩個路徑拼接在一起的意思，第二個參數不能有斜杠。因為我們要判斷一下這個文件是一個普通文件還是一個目錄，所有要先把他的絕對路徑整理出來 15 if os.path.isdir(fileAbsPath): # isdir是判斷是否為目錄，是則返回True 16 print(sp + "目錄：", fileName) # 列印當前這個文件，他是個目錄 17 getAllDir(fileAbsPath,sp = " ") # 這裡就開始遞歸了，因為我們要找到整個目錄里的東西，所以當這個文件還是個目錄的時候我們需要繼續向下找 18 else: 19 print(sp + "普通文件：", fileName) # 如果僅僅是個普通文件，那麼他裡面也就沒有其他文件了，就可以直接列印他了 20 21 22 getAllDir(path) # 這裡是調用函數，讓遍歷開始 23 24 # 最後我來說一下開始寫的那個sp，是space的意思，有人也許現在就明白了。那個其實就是讓我們方便觀察，因為每次列印都是頂行寫的，我們分不清他的目錄結構，所以通過空格來調整。在函數內部寫一個空格增加的表達式，可以使調用次數和空格數相關起來，遞歸的越深，證明目錄的級越低，那麼空格越多
三、棧模擬遞歸遍歷目錄（深度遍歷）
1 # 整體思路是沒有變得，這裡沒有寫到的也許是重覆的，看下上面註釋就好了 2 # 寫了一半想起來應該回來寫一下棧：棧就是一個容器，但它只有一個口，入棧出棧都從這一個口，而且這個棧很細，進去了就不能顛倒位置了，所以，每入棧一個元素他在最外面時候可以出來，否則得等前面的走完了它才可以出來 3 import os 4 5 def getAllDirDFS(path): 6 stack = [] # 這裡是用棧來模擬，我們先創建一個列表當做棧 7 stack.append(path) # 首先，先向棧里壓入路徑 8 9 # 處理棧，當棧為空時結束迴圈（棧為空就說明棧里沒有普通文件和目錄了，因為我們是每操作一個要把那個取出來） 10 while len(stack) != 0: 11 # 從棧中取出數據 12 dirPath = stack.pop() # pop函數是刪除最後一個元素，同時還有一個返回值，就是去除的那個元素，我們再接收一下等等用 13 # 目錄下所有文件 14 filesList = os.listdir(dirPath) # 這個和上面一樣 15 16 # 處理每一個文件，如果是普通文件則列印出來，如果是目錄則將該目錄地址壓棧 17 for fileName in filesList: 18 # print(dirPath) 19 fileAbsPath = os.path.join(dirPath,fileName) 20 # print(fileAbsPath) 21 if os.path.isdir(fileAbsPath): 22 # 是目錄就壓棧 23 print("目錄：" + fileName) 24 stack.append(fileAbsPath) # 當是目錄時入棧，它這時就在最外面，下一次迴圈時候要取出棧的元素是不是還是這個啊，既然是它的話就還有找他內部的東西，等把他找完了才繼續找和他併列的那些文件。就是說抓住一根繩子使勁往下找，找到頭沒有了才返回來，這就是深度優先遍歷 25 else: 26 # 列印普通文件 27 print("普通：" + fileName) 28 29 getAllDirDFS(path)
四、隊列模擬遞歸遍歷目錄（廣度遍歷）
1 # 這回記住了，先說一下隊列，隊是一個兩端開口的模型，一頭進一頭出，當然還有雙向隊列，迴圈等等，我們就簡單用一下最基本的隊列 2 3 import collections # 隊列在python的包里有，所以我們直接調用一下，不用以為這個很難，他也只不過是類型是queue，實際的思想是一樣的，入隊append，因為這個是在右側，也就是後方入隊，另一邊出的話就是popleft，左側出，是不是很通俗，只是改了一下出來的口 4 def getAllDirBFS(path): 5 queue = collections.deque() # 創建一個隊列，只要記得後面用法就是上面我說的那個不同就可以了 6 queue.append(path) 7 8 while len(queue) != 0: 9 dirPath = queue.popleft() # 僅僅這裡不同，因為隊列模擬是另一端出隊 10 filesList = os.listdir(dirPath) 11 for fileName in filesList: 12 fileAbsPath = os.path.join(dirPath,fileName) 13 if os.path.isdir(fileAbsPath): 14 print('目錄：' + fileName) 15 queue.append(fileAbsPath) 16 else: 17 print('文件：' + fileName) 18 19 getAllDirBFS(path) 20 21 # 大家想一下，棧是哪裡進哪裡出，也就是，剛進去的元素，接下來的一次迴圈又出來了，那便是一條路走到頭，是深度遍歷；那麼現在一頭進另一頭出是什麼意思呢，就是即便判斷了這個是一個目錄，但我現在不執行你，我要把你前面這些都查一遍，找完是目錄的都添加在後面，之後再遍歷你們這些，就是把一層的內容找完再找下一層，被稱為廣度優先遍歷。
寫這篇隨筆的時候沒有考慮到也許有些同學還需要學習一下棧和隊列，我會在之後再進行一下總結。本人也是初學者，希望和大家一起交流。
作者：漁單渠（yudanqu）
博客地址：http://www.cnblogs.com/yudanqu/
