计算机在执行递归算法时效率低的原因是什么?

一、计算机在执行递归算法时效率低的原因

计算机在执行递归算法时效率低的原因是函数调用的开销导致的。在一个函数调用之前需要做许多工作，比如准备函数内局部变量使用的空间、搞定函数的参数等等。

这些事情每次调用函数都需要做，因此会产生额外开销导致递归效率偏低，所以逻辑上开销一致时递归的额外开销会多一些

当然了，通过有意识的组织代码的写法可以把某些递归写成尾递归，尾递归可以进行特殊的优化所以效率会比普通的递归高一些，也不会因为递归太多导致栈溢出。

遍历树还不用递归的话，那么人肉写一个栈+深度优先遍历或者人肉队列+广度优先遍历，再辅以黑魔法给栈或者队列提速，应该会比递归快一些，加速幅度和语言和写法相关，但在大多数情况下我觉得是得不偿失的，花了很大精力很可能效率提升不明显。

但是，如果能转化为尾递归形式，并且你所使用的语言的编译器具有对尾递归的优化，那么尾递归的效率应该至少应该和循环一样好。当然，Java的编译器一般来说是不会对尾递归做优化的。第二，对于有些不能转化为尾递归形式的递归，即使你写成了循环的形式，其实也基本上是在拿个栈来模拟递归的过程。可能会带来一定的效率提升，但是往往会造成代码的冗余。从开发效率角度来考虑，除非性能实在达不到要求，否则还是建议使用递归的方式。

延伸阅读：

二、递归算法是什么

递归算法（英语：recursion algorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环，因此在很多函数编程语言（如Scheme）中习惯用递归来实现循环。