为了账号安全,请及时绑定邮箱和手机立即绑定

递归与迭代

递归与迭代

说到处都recursion可以使用for循环是否正确?如果递归通常较慢,那么将其用于循环迭代的技术原因是什么?并且如果总是有可能将递归转换为for循环,是否有经验法则?
查看完整描述

3 回答

?
梵蒂冈之花

TA贡献1900条经验 获得超5个赞

递归通常要慢得多,因为所有函数调用必须存储在堆栈中,以允许返回到调用者函数。在许多情况下,必须分配和复制内存以实现范围隔离。


某些优化(例如尾部调用优化)可使递归更快,但并非总是可能的,并且并非所有语言都实现。


使用递归的主要原因是


当它模仿我们对问题的处理方法时,它在许多情况下更加直观

某些数据结构(例如树)更易于使用递归进行探索(或者在任何情况下都需要堆栈)

当然,每个递归都可以建模为一种循环:这就是CPU最终将要做的事情。递归本身更直接地意味着将函数调用和作用域放在堆栈中。但是将递归算法更改为循环算法可能需要大量工作,并且会使代码的可维护性降低:至于每次优化,只有在某些分析或证据表明有必要时才应尝试进行此尝试。


查看完整回答
反对 回复 2019-11-23
?
慕田峪7331174

TA贡献1828条经验 获得超13个赞

说在各处使用递归都可以使用for循环是否正确?


是的,因为大多数CPU中的递归都是使用循环和堆栈数据结构建模的。


如果递归通常比较慢,那么使用它的技术原因是什么?


它不是“通常较慢”:递归错误地应用会较慢。最重要的是,现代编译器擅长将某些递归转换为循环,而无需询问。


并且如果总是有可能将递归转换为for循环,是否有经验法则?


编写迭代程序,以便在迭代解释时能最好地理解算法;为算法编写递归程序,最好以递归方式进行解释。


例如,经常以递归方式解释搜索二叉树,运行快速排序以及解析许多编程语言中的表达式。这些也是最好的递归编码。另一方面,就阶乘而言,计算阶乘和计算斐波纳契数更容易解释。使用递归对他们来说就像是用大锤乱打苍蝇:这不是一个好主意,即使在大锤它做了很好的工作+。


+我借用了迪克斯特拉(Dijkstra)的“编程学科”中的大锤类比。


查看完整回答
反对 回复 2019-11-23
?
红颜莎娜

TA贡献1842条经验 获得超12个赞

题 :

如果递归通常较慢,那么将其用于循环迭代的技术原因是什么?


答:

因为在某些算法中很难迭代求解。尝试以递归和迭代的方式解决深度优先搜索。您会发现很难用迭代来解决DFS。


可以尝试的另一件好事:尝试写Merge进行迭代排序。这将花费您很多时间。


题 :

说在各处使用递归都可以使用for循环是否正确?


答:

是。这个线程对此有很好的答案。


题 :

并且如果总是有可能将递归转换为for循环,是否有经验法则?


答:

相信我。尝试编写自己的版本以迭代解决深度优先搜索。您会注意到一些问题更容易递归解决。


提示:当您解决可以通过分治法解决的问题时,递归非常有用。


查看完整回答
反对 回复 2019-11-23
  • 3 回答
  • 0 关注
  • 610 浏览

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信