递归函数与使用内存使用堆栈之间的区别

我想知道递归函数与使用内存使用情况下使用堆栈之间的区别。说大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

回答