递归代码都可以转为非递归吗 ?

我们知道将递归调用全部展开后其实会形成一棵树，把递归转为非递归无非就是在遍历这棵树，那么遍历树就有很多技术了，基于栈的深度优先遍历Depth-first traversal，或者基于队列的广度优先遍历breadth-first traversal都是可以的：

说会递归转为非递归这个话题，更理论一些的解释是这样的，不管是递归还是非递归，这两者都是图灵完备的，既然是图灵完备，那么它们在表达能力上就是等价的，不存在谁不能转为谁的问题。关于图灵完备参考这篇《计算机科学中那些有趣的事实》。

只不过这存在一个难易程度的问题。大家都知道尾递归最容易转为非递归的迭代形式，本质上是这棵树不是多叉的而是单叉的，单叉的不就退化成链表了嘛，遍历链表当然是简单的，但如果是多叉的话问题就没那么简单了，这里最有趣的是不存在一种模板可以让我们直接用套路的形式把递归转为非递归，因此这里存在一个问题：为什么你要把递归转为非递归呢?

因为最终你会发现将递归转为非递归无非就是你自己接手了编译器本来已经替你完成的工作，你会发现自己在手动模拟函数调用。

递归的优势很明显：代码简洁，容易理解和维护，其为人诟病的地方在于执行效率“可能”没有非递归版本的高，但你最好理解这句话到底在说什么，到底哪里效率就不高了?我们知道函数调用本身并不是免费的，函数调用也是有代价的，这里的代价就在于维护函数调用以及函数返回需要额外执行一些指令，关于这部分的内容可以参考《​​函数调用时底层发生了什么?​​》，同时栈区空间有限，因此如果你的递归调用层级太多的话可能会导致栈溢出，撑爆你的运行时环境以及可能存在重复计算问题(可以利用memory table解决)，除此之外除非你有绝对令人信服的理由，否则你不应该试图将递归转为非递归。

网页标题：递归代码都可以转为非递归吗 ?
当前地址：http://www.hantingmc.com/qtweb/news49/348899.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联