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

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

遞歸

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

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

深度優先搜索

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

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

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

延伸閱讀：

二、回溯是什么

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

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

系統性：在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜索解空間樹；

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