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

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

遞歸

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

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

深度優(yōu)先搜索

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

正如樹的遍歷中所提到的，我們可以用 DFS 進(jìn)行 前序遍歷，中序遍歷 和 后序遍歷。在這三個(gè)遍歷順序中有一個(gè)共同的特性：除非我們到達(dá)最深的結(jié)點(diǎn)，否則我們永遠(yuǎn)不會(huì)回溯。

這也是 DFS 和 BFS 之間最大的區(qū)別，BFS永遠(yuǎn)不會(huì)深入探索，除非它已經(jīng)在當(dāng)前層級(jí)訪問了所有結(jié)點(diǎn)。

延伸閱讀：

二、回溯是什么

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

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

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

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