遍歷目錄是操作文件時的一個常見需求。比如寫一個程序，需要找到并處理指定目錄下的所有JS文件時，就需要遍歷整個目錄。

遞歸算法

遍歷目錄時一般使用遞歸算法，否則就難以編寫出簡潔的代碼。遞歸算法與數(shù)學(xué)歸納法類似，通過不斷縮小問題的規(guī)模來解決問題。以下示例說明了這種方法。

function factorial(n) {
    if (n === 1) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

上邊的函數(shù)用于計算 N 的階乘（N!）。可以看到，當(dāng) N 大于 1 時，問題簡化為計算 N 乘以 N-1 的階乘。當(dāng) N 等于 1 時，問題達(dá)到最小規(guī)模，不需要再簡化，因此直接返回 1。

陷阱： 使用遞歸算法編寫的代碼雖然簡潔，但由于每遞歸一次就產(chǎn)生一次函數(shù)調(diào)用，在需要優(yōu)先考慮性能時，需要把遞歸算法轉(zhuǎn)換為循環(huán)算法，以減少函數(shù)調(diào)用次數(shù)。

遍歷算法

目錄是一個樹狀結(jié)構(gòu)，在遍歷時一般使用深度優(yōu)先+先序遍歷算法。深度優(yōu)先，意味著到達(dá)一個節(jié)點后，首先接著遍歷子節(jié)點而不是鄰居節(jié)點。先序遍歷，意味著首次到達(dá)了某節(jié)點就算遍歷完成，而不是最后一次返回某節(jié)點才算數(shù)。因此使用這種遍歷方式時，下邊這棵樹的遍歷順序是 A > B > D > E > C > F。

          A
         / \
        B   C
       / \   \
      D   E   F

同步遍歷

了解了必要的算法后，我們可以簡單地實現(xiàn)以下目錄遍歷函數(shù)。

function travel(dir, callback) {
    fs.readdirSync(dir).forEach(function (file) {
        var pathname = path.join(dir, file);

        if (fs.statSync(pathname).isDirectory()) {
            travel(pathname, callback);
        } else {
            callback(pathname);
        }
    });
}

可以看到，該函數(shù)以某個目錄作為遍歷的起點。遇到一個子目錄時，就先接著遍歷子目錄。遇到一個文件時，就把文件的絕對路徑傳給回調(diào)函數(shù)。回調(diào)函數(shù)拿到文件路徑后，就可以做各種判斷和處理。因此假設(shè)有以下目錄：

- /home/user/
    - foo/
        x.js
    - bar/
        y.js
    z.css

使用以下代碼遍歷該目錄時，得到的輸入如下。

travel('/home/user', function (pathname) {
    console.log(pathname);
});

------------------------
/home/user/foo/x.js
/home/user/bar/y.js
/home/user/z.css

異步遍歷

如果讀取目錄或讀取文件狀態(tài)時使用的是異步API，目錄遍歷函數(shù)實現(xiàn)起來會有些復(fù)雜，但原理完全相同。travel函數(shù)的異步版本如下。

function travel(dir, callback, finish) {
    fs.readdir(dir, function (err, files) {
        (function next(i) {
            if (i < files.length) {
                var pathname = path.join(dir, files[i]);

                fs.stat(pathname, function (err, stats) {
                    if (stats.isDirectory()) {
                        travel(pathname, callback, function () {
                            next(i + 1);
                        });
                    } else {
                        callback(pathname, function () {
                            next(i + 1);
                        });
                    }
                });
            } else {
                finish && finish();
            }
        }(0));
    });
}

這里不詳細(xì)介紹異步遍歷函數(shù)的編寫技巧，在后續(xù)章節(jié)中會詳細(xì)介紹這個?？傊覀兛梢钥吹疆惒骄幊踢€是蠻復(fù)雜的。