递归和迭代方法在时间复杂度上有区别吗？

Question

我知道在递归算法和迭代算法之间确实存在空间复杂度的差异。但是，它们之间的时间复杂度是否也存在差异？例如:如果我有一个递归地计算列表中节点数量的程序，然后我实现了与迭代相同的程序，那么我在时间复杂度上是否会有任何差异，即O(n)？谢谢

Answer 1

简短的回答是:不。

除非您使用动态编程或类似方法来优化算法，否则时间复杂度不会发生变化。空间复杂度也没有变化，不知道你是从哪里得到这个想法的..

然而，在许多编程语言中，使用递归存在固有的开销，因为它们还必须存储使用更多内存的堆栈。这可能会更慢，特别是在不是尾递归的情况下。