language-agnostic - 在任何情况下我都想在递归上使用显式堆栈吗？

Question

在某些情况下，我想在我的算法中使用显式堆栈数据结构，而不是进行递归(使用调用堆栈)吗？

用一种方法比另一种方法有什么好处吗？我认为使用显式数据结构会更高效，因为它不需要方法调用，但那又是微优化领域。

Answer 1

我能想到一个你可以争论支持显式堆栈的案例:

您所处的系统可能进入和/或退出堆栈帧的成本很高，而且您的递归深度非常深。想象一下树中的深度优先。

在这样的设置中，如果您发现请求的树节点有 100 层深，如果您使用递归，则需要一个接一个地销毁 100 个堆栈帧。

使用显式堆栈，您只需从函数返回，整个堆栈将立即释放。