optimization - 递归开销-它有多严重？

Question

这个问题已经在这里有了答案:




已关闭10年。

Possible Duplicate:
Is recursion ever faster than looping?

大约15年前，我首先接受了认真学习C语言程序的培训。我的雇主想要高度优化的代码来处理计算困难的任务。我记得曾多次被建议将递归重写为循环，即使是以牺牲可读性为代价的，也要避免“递归开销”。正如我当时所了解的那样，递归开销是将数据推送到堆栈上并随后将其弹出时所需的额外工作。

现在，我使用C，Python，Perl，有时甚至是Java进行编码，而我有时想知道递归。通过重写它们还有什么收获吗？如果它们是尾部递归怎么办？现代编译器是否解决了所有这些问题？这样的关注与解释语言无关吗？

Answer 1

如果递归函数的内核在计算上比函数进入/退出代码和调用本身的开销少，则递归会导致大量开销。找出答案的最佳方法就是简单地描述两个版本的代码-一个递归，一个不递归。

也就是说，如果您避免递归的想法是自己创建一个类似堆栈的结构，请当心-它不一定比更直接的递归方法要快。同样，剖析是您的 friend 。

最后，请记住，程序员的时间比CPU的时间更昂贵。在对代码进行微优化之前，先进行测量以查看它是否真的是一个问题确实是一个好主意。