同样的算法,用递归是不是比递推慢很多

答案:3 悬赏:50 手机版

解决时间 2021-03-20 11:21

提问者网友：那叫心脏的地方装的都是你
2021-03-20 03:06

同样的算法,用递归是不是比递推慢很多

最佳答案

五星知识达人网友：撞了怀
2021-03-20 04:12

如果单纯的递归一定会慢很多,因为你计算时反复计算了一些值,浪费了相当多的时间,
但是优化之后的递归和地推效率基本一样,虽然递归要进栈出栈花费时间,且容易因递归深度过大而栈溢出.

所谓的优化,就是记忆化,比如递归函数是f(a,b)
那么弄一个数组,f_r[a,b]
每次运行递归函数f(a,b)时,检测f_r[a,b]的值是否已定义,是则返回这个值,否则执行函数,且在函数返回前记录返回值到f_r[a,b]中.

全部回答

1楼网友：猎心人
2021-03-20 05:32

是的
递归每次进入就是调用子程序,必然慢.而且要不断开内存.
.多了自然影响速度.

2楼网友：未来江山和你
2021-03-20 04:48

递推和递归比较有意思,简单的说,递推是在借助前一个几经计算出来的结果去计算下一步的结果,以此来得到最终结果,有此可知递推并不需要保留太多现场信息,
而递归就不一样,虽然也是要借助前一步的结果,但这前一步结果往往刚开始是未知的,要一步一步递推下去,直到遇到终结条件,然后在一层一层的回归,直到回归到最上一层计算出结果,可见递归是包含两步的,一个递推下去,一个在回归 ,
递归往往表达简单 ,但计算需要时空都比较大

我要举报

如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！