performance - 递归与手动堆栈 - 在哪种情况下首选哪个？

Question

递归程序在内部创建堆栈，并导致用户编写更少的代码。

由于上述以外的原因，是否存在递归实际上优于手动堆栈的情况？

编辑1：

动态内存分配以何种方式比递归程序在堆上的分配更“昂贵”？

Answer 1

当你说“更少的代码”时，我认为你暗示的主要原因是设计的清晰和简单。在具有局部变量和自动存储等功能的语言中，使用这些功能比将所有内容构建成家庭滚动堆栈要自然得多。（毕竟，为什么要使用函数？为什么不使用if/else和while作为唯一的控制结构来编写整个程序？）

另一个考虑因素是性能，尤其是在多线程环境中。递归 - 取决于语言 - 可能会使用堆栈（注意：您说“在内部创建堆栈”，但实际上，它使用此类语言中的程序始终具有的堆栈），而手动堆栈结构将需要动态内存分配，这通常会带来明显的性能损失——更不用说确保在（比如说）遇到异常时释放所有内存所增加的复杂性。

Answer 2

我大多同意@ruakh 的回答。我只想补充一点，使用系统堆栈有很多开销（实际上，每次递归时，你推送的状态比你需要的多得多），并且可能会导致非常深（但有界）递归的堆栈溢出，你可能能够通过使用显式堆栈并仅推送您需要的状态来避免。

Answer 3

在外部使用堆栈

vector<int> Solution::inorderTraversal(TreeNode* A) {
vector<int> res;
stack<TreeNode* > st;
TreeNode* root=A;
while(true)
{
    if(root==NULL)
    {
        if(st.empty())
        break;
        root=st.top();
        st.pop();
        res.push_back(root->val);
        root=root->right;


    }
    else
    {

        st.push(root);
        root=root->left;
    }
}
return res;

}

使用递归

void inorder(struct node* root)

但是在这里我们看到外部堆栈的使用节省了大量的处理时间，因此外部堆栈方法更快。