递归效率低的原因

echosoar 原创发表于 2015/09/05 16:56:01
#算法

递归效率低是函数调用的开销导致的。

在一个函数调用之前需要做许多工作,比如准备函数内局部变量使用的空间、搞定函数的参数等等,这些事情每次调用函数都需要做,因此会产生额外开销导致递归效率偏低,所以逻辑上开销一致时递归的额外开销会多一些 当然了,通过有意识的组织代码的写法可以把某些递归写成尾递归,尾递归可以进行特殊的优化所以效率会比普通的递归高一些,也不会因为递归太多导致栈溢出 如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时,这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作,这个特性很重要,因为大多数现代的编译器会利用这种特点自动生成优化的代码。 遍历树还不用递归的话,那么人肉写一个栈+深度优先遍历或者人肉队列+广度优先遍历,再辅以黑魔法给栈或者队列提速,应该会比递归快一些,加速幅度和语言和写法相关,但在大多数情况下我觉得是得不偿失的,花了很大精力很可能效率提升不明显