递归程序会在内部创建一个栈,使用户编写的代码更少。
除了上述原因之外,是否有任何情况下递归实际上比手动堆栈更可取?
编辑1:
与递归程序中的堆栈分配相比,动态内存分配在哪些方面更“昂贵”?
递归程序会在内部创建一个栈,使用户编写的代码更少。
除了上述原因之外,是否有任何情况下递归实际上比手动堆栈更可取?
与递归程序中的堆栈分配相比,动态内存分配在哪些方面更“昂贵”?
我大部分同意@ruakh的答案。我只想补充一点,使用系统堆栈会有很多开销(每次递归实际上都要推送比你需要的更多状态),并且可能会导致非常深但有限的递归堆栈溢出,您可以通过使用显式堆栈并仅推送所需状态来避免这种情况。
使用外部堆栈
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)