什么时候以及为什么递归的性能比迭代差？

Question

什么时候以及为什么递归的性能比迭代差？

最近我在面试时被问到这个问题。我的答案是，当递归的深度很大时，递归的性能会更差。面试官似乎在期待一个不同的答案。有没有人能多解释一下。

Answer 1

可能有很多原因；有一些原因浮现在脑海中：

• 递归深度很大递增的堆栈使用时间用于卷积和展开堆栈，堆栈消耗的内存较少，而迭代使用不使用更多资源(包括堆栈)的跳转命令
• 递归函数保留大量状态(例如局部变量)，直到递归完成(另一方面，每次迭代都会丢弃局部变量)，再次为后续的递归

留下较少的可用内存

Answer 2

根据您所说的，您已经回答了问题的When部分：

当递归深度较大时为

但没有回答为什么的部分，所以你只回答了面试官问题的一半。