我想知道遞歸函數與使用內存使用情況下使用堆棧之間的區別。 說大DFS哪個更有效率。遞歸函數與使用內存使用堆棧之間的區別
回答
一個明確的堆棧數據結構在理論上應使用略更少的內存,作爲一個遞歸函數總是有每次調用一些額外的開銷,返回地址等
我會假設你要討論相同算法的兩種方法之間的差異。我們有一個圖G =(V,E)其中V是一組頂點並且E是一組頂點對,我們在圖上通過以下任一方式運行深度優先搜索(DFS):
- 使用遞歸方法,其中
visit
方法遞歸調用自身。 - 在循環中使用顯式堆棧。
這兩種方法,對大的,使用相同的空間量,O(d)其中d是DFS搜索樹的深度(它是由最長的可能的非循環路徑爲界在
圖。通常一個明確的堆棧將使用少略內存保羅 - [R寫入,另外重要的一點是,在許多語言中,函數調用棧是非常有限的,如果它的增長也將中止程序在堆中管理的顯式堆棧並不構成類似的問題。爲了獲得略微雖然內存使用量較少,但您必須將堆棧表示爲數組。如果你把它表示爲一個鏈表,它可能不會更好。它甚至可能會稍微惡化。
我打算用另一種方式,至少在編譯語言中。遞歸函數,以高效率編寫,可以比明確的堆棧做得更好。編譯器可以使用擁有它們的CPU的棧幀操作原語來更高效地執行操作。
這一觀點得到支持「垃圾回收快,但堆棧更快」,由詹姆斯·小號米勒和Guillermo Rosaz:http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.2789
我認爲你的意思是在時間方面的效率。我用記憶的方式問 – ashmish2 2011-02-28 17:28:09
- 1. 數組和堆棧之間的區別?
- 2. 在遞歸函數中存儲堆棧
- 3. 我在使用的std ::堆棧以遞歸函數檢索值
- 4. 如何將遞歸函數轉換爲使用堆棧?
- 5. 非遞歸析構函數二叉搜索樹使用堆棧
- 6. 使用遞歸溢出堆棧
- 7. 即使遞歸調用在函數結束時堆棧級別太深?
- 8. 堆棧上的遞歸函數
- 9. 使用堆棧的河內Python解決方案的遞歸塔
- 10. 遞歸函數堆棧溢出
- 11. 堆中的對象與堆棧內存之間的混淆
- 12. 使用遞歸函數堆棧 - 在Scala中使用Free Monads Trampoline安全嗎?
- 13. 回溯和遞歸之間的區別?
- 14. 如何跟蹤遞歸函數的調用堆棧使用情況
- 15. 遞歸Java - 堆棧
- 16. .NET EXE和DLL之間的堆棧/堆區別
- 17. 遞歸時堆棧級別太深(SystemStackError)
- 18. jQuery遞歸函數調用和Javascript的setInterval之間有區別嗎?
- 19. Lisp中遞歸函數調用的堆棧溢出
- 20. 由遞歸函數佔用的堆棧大小維
- 21. 關於堆棧和堆棧內存使用的問題
- 22. 進程虛擬內存 - 堆棧和堆之間的空間
- 23. 堆棧和堆之間有什麼區別?
- 24. 使用Javascript類函數執行15次遞歸後的堆棧溢出
- 25. 函數與遞歸導致堆棧溢出
- 26. 將遞歸函數中的setTimeOut函數導致堆棧溢出?
- 27. 使用可選參數F#重載函數之間的區別
- 28. 堆棧缺少遞歸調用Java的
- 29. Wicket,頁面堆棧和內存使用
- 30. PHP - 使用和不使用內存方法的對象之間的區別?
編譯器將您的遞歸程序轉換成一個迭代,從而創造一個明確的堆棧:) – 2011-03-01 08:11:59