要理解深度優先搜索必須理解遞歸的本質，遞歸的核心思想在于在一個函數還沒有執行完成的時候就調用自身，這樣就會形成一個樹狀的結構，從而使其可以一直延伸下去，進而覆蓋所有可能的分支。直到某一層遞歸條件滿足，才開始收斂。

Figure 1 遞歸

Note：圖中序號相同而且用虛線相連接的一個方塊和圓圈對表示一次函數調用

從圖中可以看出遞歸具有很強的可回退性和選擇性，圖中的2和2’是一次遞歸的不同分支，3和3’是一次遞歸的不同分支。函數執行到某一層次之后完全可以選擇任何一個分支進行收斂，這點剛好符合深度優先搜索的需求。

寬度優先搜索算法（BFS）

寬度優先搜索算法，其本質則是基于樹狀結構，每到一層，先把該層所有的未遍歷的節點添加到隊列，再判斷每一個節點是否滿足條件，如果滿足退出即可，否則，再到下一層繼續遍歷。

在遍歷的過程中每一層的遍歷都在上一層遍歷的后面，這一點正是隊列的特點——先把一個節點對應的下一層可達的節點全部添加到隊列尾，繼續遍歷上一層的隊列，上一層結束后遍歷下一層的節點。

總結

這兩種搜索算法都能夠生成所有能夠遍歷到的狀態，因而在需要對所有狀態進行處理時使用寬度優先搜索算法時是可以的。但是使用遞歸函數則實現比較簡單 一點，而且狀態的管理也更簡單。故而一般還是使用深度優先搜索算法實現。但是在求最短路徑的時候一般還是使用寬度優先搜索算法。

寬度優先搜索算法一般會把狀態逐個添加到隊列中，也就是說內存與狀態數成正比，而深度優先搜索算法則是與最大遞歸數成正比，所以一般認為深度優先搜索算法更為節省內存。

來自：http://www.cnblogs.com/tianyou/p/4695452.html