經典（基於遞歸的）深度首先搜索比基於堆棧的DFS更高的內存效率？

Question

我正在查看@AndreyT對this問題的回覆，我對經典DFS與基於堆棧的DFS的內存效率有個疑問。爭論是傳統的回溯DFS不能通過簡單的堆棧到隊列替換從BFS創建。在通過堆棧到隊列替換來執行BFS到DFS時，會損失傳統DFS的空間效率。不是一個搜索算法專家（雖然我正在閱讀它），但我會認爲這只是「真實的」並隨之而來。

但是，我的問題實際上是關於整體內存效率。雖然遞歸解決方案確實具有一定的代碼效率（我可以通過幾行遞歸搜索代碼做更多的事情）和優雅，但是它沒有內存（可能性能）「打」，因爲它是遞歸？

每當你遞歸到函數中時，它會將本地數據壓入堆棧，函數的返回地址以及編譯器認爲維護返回狀態所需的任何其他內容等。這可以快速加起來。它也必須爲每個遞歸做一個函數調用，它也吃掉了一些操作（也許很少......或者它可能會破壞分支的可預測性，從而迫使管道刷新......這裏不是專家......隨意幫腔）。

我想我現在想堅持簡單的遞歸，而不是像這個問題的答案那樣進入像尾遞歸這樣的「替代形式」。最起碼到現在。

Answer 1

雖然你可以可能通過顯式管理堆棧比編譯器做得更好，但獎勵往往不值得花費額外的工作。現在編譯器比許多人想象的要聰明得多。他們的表現也不如別人認爲的那麼好 - 你把壞事看好。

也就是說，大多數編譯器可以檢測並刪除尾遞歸。有些可以將簡單的遞歸函數轉換爲迭代解決方案，並且一些非常好的編譯器可以發現局部變量可以被重用。

遞歸解決方案通常會導致代碼更小，這意味着代碼更適合放入CPU緩存。與「慢」遞歸解決方案相比，需要顯式託管堆棧的非遞歸解決方案會導致更大的代碼，更多的緩存未命中以及更慢的性能。

最後，許多解決方案都是以最直觀的方式遞歸實現的，而且這些解決方案往往比較簡單易懂。將遞歸解決方案轉換爲涉及明確管理堆棧的迭代解決方案會產生更多的代碼行，這些代碼行通常模糊不清，難以證明是正確的。

我發現一個簡單的代碼和理解遞歸解決方案通常足夠快，不會使用太多的內存。在極少數情況下，剖析顯示我的遞歸實現是瓶頸（通常它是一個比較函數或類似於遞歸函數調用的），我會考慮一個非遞歸解決方案。我通常不會通過改變來實現重大收益。