遍歷目錄是操作文件時的一個常見需求。比如寫一個程序，需要找到并處理指定目錄下的所有JS文件時，就需要遍歷整個目錄。
## 遞歸算法
遍歷目錄時一般使用遞歸算法，否則就難以編寫出簡潔的代碼。遞歸算法與數學歸納法類似，通過不斷縮小問題的規模來解決問題。以下示例說明了這種方法。
~~~
function factorial(n) {
if (n === 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}
~~~
上邊的函數用于計算N的階乘（N!）。可以看到，當N大于1時，問題簡化為計算N乘以N-1的階乘。當N等于1時，問題達到最小規模，不需要再簡化，因此直接返回1。
> **陷阱：**?使用遞歸算法編寫的代碼雖然簡潔，但由于每遞歸一次就產生一次函數調用，在需要優先考慮性能時，需要把遞歸算法轉換為循環算法，以減少函數調用次數。
## 遍歷算法
目錄是一個樹狀結構，在遍歷時一般使用深度優先+先序遍歷算法。深度優先，意味著到達一個節點后，首先接著遍歷子節點而不是鄰居節點。先序遍歷，意味著首次到達了某節點就算遍歷完成，而不是最后一次返回某節點才算數。因此使用這種遍歷方式時，下邊這棵樹的遍歷順序是`A > B > D > E > C > F`。
~~~
A
/ \
B C
/ \ \
D E F
~~~
## 同步遍歷
了解了必要的算法后，我們可以簡單地實現以下目錄遍歷函數。
~~~
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);
}
});
}
~~~
可以看到，該函數以某個目錄作為遍歷的起點。遇到一個子目錄時，就先接著遍歷子目錄。遇到一個文件時，就把文件的絕對路徑傳給回調函數。回調函數拿到文件路徑后，就可以做各種判斷和處理。因此假設有以下目錄：
~~~
- /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
~~~
## 異步遍歷
如果讀取目錄或讀取文件狀態時使用的是異步API，目錄遍歷函數實現起來會有些復雜，但原理完全相同。`travel`函數的異步版本如下。
~~~
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));
});
}
~~~
這里不詳細介紹異步遍歷函數的編寫技巧，在后續章節中會詳細介紹這個。總之我們可以看到異步編程還是蠻復雜的。
