遞歸函數與使用內存使用堆棧之間的區別

我想知道遞歸函數與使用內存使用情況下使用堆棧之間的區別。說大DFS哪個更有效率。遞歸函數與使用內存使用堆棧之間的區別

2011-02-28 ashmish2

編譯器將您的遞歸程序轉換成一個迭代，從而創造一個明確的堆棧:) – 2011-03-01 08:11:59

一個明確的堆棧數據結構在理論上應使用略更少的內存，作爲一個遞歸函數總是有每次調用一些額外的開銷，返回地址等

2011-02-28 17:12:43

我會假設你要討論相同算法的兩種方法之間的差異。我們有一個圖G =（V，E）其中V是一組頂點並且E是一組頂點對，我們在圖上通過以下任一方式運行深度優先搜索（DFS）：

這兩種方法，對大的，使用相同的空間量，O（d）其中d是DFS搜索樹的深度（它是由最長的可能的非循環路徑爲界在

圖。通常一個明確的堆棧將使用少略內存保羅 - [R寫入，另外重要的一點是，在許多語言中，函數調用棧是非常有限的，如果它的增長也將中止程序在堆中管理的顯式堆棧並不構成類似的問題。爲了獲得略微雖然內存使用量較少，但您必須將堆棧表示爲數組。如果你把它表示爲一個鏈表，它可能不會更好。它甚至可能會稍微惡化。

2011-02-28 17:22:00

我打算用另一種方式，至少在編譯語言中。遞歸函數，以高效率編寫，可以比明確的堆棧做得更好。編譯器可以使用擁有它們的CPU的棧幀操作原語來更高效地執行操作。

這一觀點得到支持「垃圾回收快，但堆棧更快」，由詹姆斯·小號米勒和Guillermo Rosaz：http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.2789

2011-02-28 17:23:46

我認爲你的意思是在時間方面的效率。我用記憶的方式問 – ashmish2 2011-02-28 17:28:09

回答