递归潜在的风险

二叉树的遍历可以通过递归实现，下面是二叉树的先序遍历。

void preOrder(BiTree* root)
{
if (root != NULL)
{
visit(root);
preOrder(root->lchild);
preOrder(root->rchild);
}
}

  递归算法存在一个问题：当递归层数过深时，有可能产生栈溢出，例如，如果二叉树只有几百个节点，那么通过递归实现没有问题，但是如果二叉树有几百万个节点，使用递归就可能会发生栈溢出。
  在递归调用过程中，每一次递归调用都会保留现场，把当前的上下文压入函数栈，随着递归调用层数的深入，压入函数栈的内容会越来越多，直到函数栈的空间用尽，而递归程序仍然没有满足返回的条件，继续向更深的一层调用，就会发生栈溢出。
  这是递归自身的缺陷。虽然递归函数书写简单，可读性强，但是只要编写递归函数，就要考虑到栈溢出的风险。为了避免栈溢出，可以用循环代替递归。原则上任何递归都可以用循环的方式实现，虽然使用循环会造成代码变长，可读性降低，但是避免了栈溢出的问题。

void preOrder(BiTree* root)
{
stack<BiTree*> s;
BiTree* p = root;
while (p != NULL || !s.empty())
{
while (p != NULL)
{
visit(p);
s.push(p);
p = p->lchild;
}
if (!s.empty())
{
p = s.top();
s.pop();
p = p->rchild;
}
}
}

上面的代码通过循环实现了二叉树的先序遍历，代码明显比递归长了不少，逻辑也更加复杂，但是通过循环替代了递归，提高了程序的健壮性。

最后

以上就是简单台灯为你收集整理的递归潜在的风险的全部内容，希望文章能够帮你解决递归潜在的风险所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。