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

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

遞歸

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

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

深度優(yōu)先搜索

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

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

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

延伸閱讀：

二、回溯是什么

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

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

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

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