你瑞哥 2013-09-04 03:10 采纳率: 0%
浏览 2145

递归调用循环的非递归形式

背景:之前在算法书上看到说所有的递归算法都可以写成非递归的形式。
那么遍历一个完全树的所有叶子节点,我看过两个算法,一个是递归调用,非常简单。
还有一个使用了队列:(c++ 和伪代码的混合表示)
queue.push(root);//根节点进队
while (!queue.isEmpty())
{
queue.push(root->left);
queue.push(root->right);
if (!queue.top()->hasChild())
{
print queue.top()->data;
}
queue.pop();
}

上面的算是非递归形式。

不过我想问的是,是不是说一定需要队列或者堆栈这样的辅助数据结构才能解决该问题?
因为我觉得之前的一些递归算法改成的非递归算法都没有用到什么数据结构。
比如合并排序的非递归形式。用到的仅仅是两个向量而已。
我一直认为递归算法改成非递归形式是有一定的模板可循的。如果辅助数据结构不可避免,是不是意味着所有的递归算法只是理论上可以写成递归形式,至于写不写的出来,还要看个人的数据结构水平?

  • 写回答

1条回答 默认 最新

  • Coursera 2014-12-05 00:55
    关注

    递归变成非递归,栈和队列是标准的支持数据结构,因为函数调用就是用堆栈实现的。

    评论

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 MATLAB动图问题
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名