一、同樣的深度優(yōu)先搜索，使用棧和使用遞歸的性能差別

同樣的深度優(yōu)先搜索，使用棧和使用遞歸的性能差別是，對于內存，棧的內容太多了。只壓棧的話i和target應該夠了，棧的內容只需要和DP的參數一樣多。

遞歸

遞歸的基本思想是，把規(guī)模較大的一個問題，分解成規(guī)模較小的多個子問題去解決，而每一個子問題又可以繼續(xù)拆分成多個更小的子問題。最重要的一點就是假設子問題已經解決了，現在要基于已經解決的子問題來解決當前問題；或者說，必須先解決子問題，再基于子問題來解決當前問題。

遞歸解決的是有依賴順序關系的多個問題：假設一個抽象問題有兩個時間點要素：開始處理，結束處理，那么遞歸處理的順序就是，先開始處理的問題，最后才能結束處理。遞歸對問題的處理順序，是遵循了先入后出（也就是先開始的問題最后結束）的規(guī)律。

深度優(yōu)先搜索

深度優(yōu)先搜索（DFS）是用于在樹/圖中遍歷/搜索的另一種重要算法。也可以在更抽象的場景中使用。

正如樹的遍歷中所提到的，我們可以用 DFS 進行 前序遍歷，中序遍歷 和 后序遍歷。在這三個遍歷順序中有一個共同的特性：除非我們到達最深的結點，否則我們永遠不會回溯。

這也是 DFS 和 BFS 之間最大的區(qū)別，BFS永遠不會深入探索，除非它已經在當前層級訪問了所有結點。

延伸閱讀：

二、回溯是什么

回溯法采用試錯的思想，它嘗試分步的去解決一個問題。在分步解決問題的過程中，當它通過嘗試發(fā)現現有的分步答案不能得到有效的正確的解答的時候，它將取消上一步甚至是上幾步的計算，再通過其它的可能的分步解答再次嘗試尋找問題的答案。

回溯法是一個既帶有系統(tǒng)性又帶有跳躍性的搜索算法：

系統(tǒng)性：在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結點出發(fā)搜索解空間樹；

跳躍性：算法搜索至解空間樹的任一結點時，判斷該結點為根的子樹是否包含問題的解，如果肯定不包含，則跳過以該結點為根的子樹的搜索，逐層向其祖先點回溯，否則，進入該子樹，繼續(xù)深度優(yōu)先的策略進行搜索。