最重要的速度问题

Question

我正在参加阿尔·齐默尔曼的编程大赛。

http://www.azspcs.net/Contest/SonOfDarts

我写了一个递归算法，但它需要很长时间才能运行。我想知道，关于递归算法的速度，最重要的考虑因素是什么。我已经将大多数属性设置为全局的，这样它们就不会在每次执行递归步骤时都被分配。我还能做些什么，在不改变算法的情况下加速我的程序吗？

Answer 1

这取决于你的算法的细节。如果它是 tail recursive ，你可以很容易地把它转换成迭代算法。

Answer 2

递归总是比迭代慢。由于堆栈/堆/内存分配的原因，分配执行的速度比大多数都要慢。在复杂的算法中实现递归函数总是很容易的，但如果可能的话，递归函数会更快。

Answer 3

你用什么语言写你的程序？一些语言，如Haskell，是为递归算法量身定做的，而其他语言，如Python，则不是。

每次函数调用花费了多少时间，与函数外的递归调用次数相比？在函数中执行的代码太少肯定会导致性能损失。

堆栈上的变量通常比全局变量快得多。考虑将它们从一个函数传递到另一个函数，而不是放在全局函数中。

不幸的是，问题中没有足够的上下文来提供更好的答案。

递归算法也可以设计成尾递归的。在这种情况下，编译器支持尾递归优化，从而使代码更快。