文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

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

2024-12-02 04:09

关注

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

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

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

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

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

来源:码农的荒岛求生内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯