2 mny316 mny316 于 2013.09.04 11:10 提问

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

背景:之前在算法书上看到说所有的递归算法都可以写成非递归的形式。
那么遍历一个完全树的所有叶子节点,我看过两个算法,一个是递归调用,非常简单。
还有一个使用了队列:(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个回答

eagleyan
eagleyan   Rxr 2014.12.05 08:55

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

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!