递归何时比迭代性能差？为什么？

Question

什么时候以及为什么递归比迭代执行得更差？

最近我在面试中被问到了这个问题。我的回答是当递归的深度很大时，递归执行会变得更慢。但是面试官似乎期望得到一个不同的答案。请有经验的人士给出更详细的解释。

- softwarematter

---

也许他们期望的答案是过早优化是浪费时间的，你应该编写清晰易懂的代码，只有在实际证明存在瓶颈时才进行优化。无论哪种方式，你都可以提出一些很棒的理论答案，但最终，所有这些答案在现实世界中都是无关紧要的。 - Cody Gray

也许她希望你谈论一下尾递归优化？ - MK.

递归：最快速的方法 当处理树形结构或者有递归定义的问题时，递归是一种自然的解决方案。但是，在某些情况下，递归可能会非常慢，甚至比迭代更慢。这可能是由于递归堆栈的开销或重复计算造成的。 换句话说，递归不是银弹，但在适当的情况下可以是最优解决方案。 - NotMe

@M.Babcock 这不是重复的问题。我已经看到那个问题了。这个问题问的是原因。 - softwarematter

那个会给你原因。仔细再读一遍 Paul 的回答。注意链接。 - Cody Gray

Answer 1

可能有很多原因；以下是一些可能的原因：

• 递归深度较大，增加了堆栈使用量 - 时间花费在绕圈和解开堆栈上，并且堆栈消耗内存，每次递归留下更少的内存，而迭代使用不会使用更多资源（包括堆栈）的JUMP命令
• 递归函数保存了许多状态（例如局部变量），必须将其保留在内存中，直到递归完成（另一方面，迭代在每次迭代时都会丢弃本地变量），再次留下较少的可用内存用于每个后续递归

- D Stanley

Answer 2

根据你所说的，你已经回答了问题中的“何时”部分：

当递归深度很大时

但是你没有回答问题中的“为什么”部分，因此你只回答了面试官问的一半问题。

- jdigital