递归和手动堆栈 - 在哪种情况下更受青睐？

Question

递归程序会在内部创建一个栈，使用户编写的代码更少。

除了上述原因之外，是否有任何情况下递归实际上比手动堆栈更可取？

编辑1：

与递归程序中的堆栈分配相比，动态内存分配在哪些方面更“昂贵”？

- Aquarius_Girl

---

如果您的递归没有超过堆栈大小，那么您只是在使用调用栈而不是堆。 - qwr

Answer 1

主要原因，当你说“更少的代码”时，我认为你指的是设计的清晰性和简单性。在具有本地变量和自动存储等功能的语言中，使用这些特性比将所有内容结构化为自制堆栈要自然得多。(毕竟，为什么要使用函数呢？为什么不只使用if/else和while作为您唯一的控制结构来编写整个程序呢？)

另一个考虑因素是性能，特别是在多线程环境中。递归-根据语言-很可能会使用堆栈(注意：你说“内部创建堆栈”，但实际上，它使用的是程序在这些语言中始终拥有的堆栈)，而手动堆栈结构则需要动态内存分配，这经常会产生明显的性能损失-更不用说确保您在遇到异常时释放所有内存的额外复杂性了。

- ruakh

---

使用系统栈的性能优势是可观的，但你需要做出一定的权衡，因为相对于堆上的堆栈数据结构，系统栈的递归深度通常会受到更大的限制。这是因为堆要比栈大得多。 - Seth Carnegie

@SethCarnegie：是的，绝对没错，说得好。在许多平台上，堆内存耗尽比溢出栈更易于处理。由于问题严格限制在使用递归的原因上，我没有提到这些事情，但也许我应该为了完整性而提一下？ - ruakh

动态内存分配在什么情况下会变得“昂贵”？难道不只是关于分配和释放内存吗？ - Aquarius_Girl

如何决定两者中哪一个更昂贵？这应该是一个单独的问题吗？ - Aquarius_Girl

@ruakh 非常有趣。您测试过在系统栈上分配固定大小数组 (作为堆栈) 时它的速度有多快吗？有时可以对递归深度进行上限约束。 - qbt937

Answer 2

我大部分同意@ruakh的答案。我只想补充一点，使用系统堆栈会有很多开销（每次递归实际上都要推送比你需要的更多状态），并且可能会导致非常深但有限的递归堆栈溢出，您可以通过使用显式堆栈并仅推送所需状态来避免这种情况。

- MAK

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)

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

- Naman Lashkari

---

void inorder(struct node* root) { if(root != NULL) { inorder(root->left); cout << root->val; inorder(root->right); } } - Naman Lashkari