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

发布网友发布时间：2022-04-30 18:42

共3个回答

热心网友时间：2022-06-30 01:13

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

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

热心网友时间：2022-06-30 01:13

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

热心网友时间：2022-06-30 01:14

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