Python 遞迴處理路徑下檔案與資料夾

取得某個路徑下的所有檔案與資料夾是經常會使用到的功能，尤其是在寫一些小工具來處理硬碟上的檔案時。早先我都是用傳統寫 C++ 的方式來思考，所以在 Python 的文件中找到了 listdir() 這個函式，然後寫了類似以下的代碼：

import os

def doInDir(somedir):
    print somedir
    fileList = os.listdir(somedir)
    for f in fileList:
        fullpath = os.path.join(somedir, f)
        if os.path.isdir(fullpath):
            doInDir(fullpath)
        elif os.path.isfile(fullpath):
            print fullpath

doInDir("/tmp/")

不過最近發現在 Python 下做事其實可以更簡單，內建的 os.walk() 就提供了非常強大的功能，使用的方式如下：

import os

for root, dirs, files in os.walk("/tmp/"):
    print root
    for f in files:
        print os.path.join(root, f)

相比之下，同樣的功能用 os.walk() 就精簡了許多。上面兩段程式碼做的事情基本上是一樣的，都是列出指定資料夾下的所有檔案與子資料夾；不過有個小小地方需要注意一下，就是用兩種方法索處理的內部順序並不相同。listdir() 會按照深度優先搜索的順序，一層一層往下深入，其中檔案與資料夾的先後順序是交替穿插的；而 os.walk() 因為把檔案與文件夾都歸類好放在各自的 list 中，因此兩者的處理是分開的。以下是上面兩段程式針對同一個範例資料夾的輸出，可以看出處理順序的不同。

os.walk()

/testtree/
/testtree/1file
/testtree/3file
/testtree/2dir
/testtree/2dir/21file
/testtree/2dir/24file
/testtree/2dir/22dir
/testtree/2dir/22dir/221file
/testtree/2dir/23dir
/testtree/4dir

os.listdir()

/testtree/
/testtree/1file
/testtree/2dir
/testtree/2dir/21file
/testtree/2dir/22dir
/testtree/2dir/22dir/221file
/testtree/2dir/23dir
/testtree/2dir/24file
/testtree/3file
/testtree/4dir

To Iterate is Human, to Recurse, Divine

今天偶然看到這句話，"To iterate is human, to recurse, divine."，無巧不巧，最近幾天的課程我也剛好在講解遞迴的概念。

說這句話的老兄是 L. Peter Deutsch，雖然他的姓寫作是「德意志（Deutsch）」，可是這位德意志先生卻是個道道地地的美國麻省人。Deutsch 在電腦界最主要的貢獻就是 Ghostscript 和 Archie。Ghostscript 是可以用來生成 PDF 或是 Postscript 格式文件的軟體，從 1988 第一版釋出一直到今年 2011 橫跨了 23 個年頭，仍然持續開發維護中（當然維護者早已換人接手，不再是 Deutsch 了），也衍生了許多分支專案。

而關於另一項成就 Archie 可能聽過的人就比較少了，因為這是早年的一項網路服務，如同 Gopher 或是 News 一樣，早已淹沒在歷史的洪流中。在大家都還是以 FTP 作為主要下載方式的年代裡，Archie 可以整合不同匿名 FTP 站台的資訊，建立各站台擁有檔案的索引，然後使用者只要上連 Archie 網站，輸入檔名進行搜尋，就可以知道自己想要的檔案可以從哪個 FTP 站台下載。聽起來很像搜尋引擎做的工作不是？沒錯，Archie 某種程度上可說是網頁搜尋引擎的前身。早在 Google 甚至 Yahoo! 出生之前，Archie 就已經在 Internet 上運作好一段時間了。對這段歷史有興趣的可以看看這篇：The first search engine, Archie.

回頭來看看篇首這句：

"To iterate is human, to recurse, divine"

這句到底代表什麼意思，著實讓我推敲了很久。先來看看網路找來的兩個我覺得不錯的翻譯（原譯者均不明）：

“迭代（iterate）者为人，递归（recurse）者为神。”

「遞迴（recurse）只應天上有, 凡人該當用迴圈（iterate）」

同樣一句話，將其放在不同情境下會有截然不同的解讀。這句的意思到底是要說「我們應該放棄平凡的作法，盡量使用遞迴，以追求神的境界」呢？還是想表達「遞迴這種作法太神乎奇技了，我們應該用簡單、平凡，一般人都可以接受的作法，以迴圈來實現」呢？

我參透不出這句話到底是推崇遞迴還是鼓勵迴圈。不過以我的經驗而言，遞迴雖然一開始很容易讓人腦筋打結，可是當熟悉遞迴之後，許多複雜的處理都會變得簡單明瞭。許多程式機制的實作擺脫不了遞迴，比方說遍歷某資料夾下的所有子資料夾與檔案、迷宮路徑的搜尋，或是 AI 決策樹的判斷，使用遞迴來寫可以達到事半功倍的效果。

當然，所有的的遞迴都可以改寫成迴圈形式，改寫為迴圈形式通常也可以獲得效率上的提升，因為遞迴層層呼叫的過程中不停將資料塞入堆疊又從堆疊取出的手續太耗成本，遠不如迴圈以少數幾個變數就可以控制完整的流程。但是將遞迴改寫成迴圈的形式往往會失去邏輯的簡潔與結構的優雅。

寫程式經常就是遇到這種兩難：要嘛對電腦好，讓它少算一點，少用點空間；要嘛對人好，電腦多做點工，可是人類看起 Code 來輕鬆（話說遞迴也不見得都比迴圈式的改寫好懂就是）。因此，針對同一件事情，該用遞迴解還是迴圈解好呢？我想，選擇自己與他人都容易理解的方法去做，那就對了。