|
|
为什么说递归效率低？
关注者
568
被浏览
198,587
43 个回答
知乎用户
递归效率低是函数调用的开销导致的。
在一个函数调用之前需要做许多工作，比如准备函数内局部变量使用的空间、搞定函数的参数等等，这些事情每次调用函数都需要做，因此会产生额外开销导致递归效率偏低，所以逻辑上开销一致时递归的额外开销会多一些
当然了，通过有意识的组织代码的写法可以把某些递归写成尾递归，尾递归可以进行特殊的优化所以效率会比普通的递归高一些，也不会因为递归太多导致栈溢出
遍历树还不用递归的话，那么人肉写一个栈+深度优先遍历或者人肉队列+广度优先遍历，再辅以黑魔法给栈或者队列提速，应该会比递归快一些，加速幅度和语言和写法相关，但在大多数情况下我觉得是得不偿失的，花了很大精力很可能效率提升不明显
之前做 RapidJSON 时，解释器用递归下降方式，由于没有限定层数，有机会做极深的 JSON 请求来引发 stack overflow（如 "[[[[[...]]]]]" 一百万层），产生安全性及稳定性问题。
之后同事再写多了一个版本，就是自行实现 stack （所谓的用迭代取代递归），只要有足够的 heap 就不会有问题。当然，在这个个例上，也可以简单地限制层数来解决。
递归的额外耗时决于函数调用的成本，这成本与具体平台相关。
许多时候，可以尾调用的递归还不如显式写作迭代。不可以尾调用的递归，要换作迭代方式就需要自建 stack，较为复杂，但有可能降低时间和空间的系数，并且能支持更大的深度。