递归和迭代方法之间是否存在时间复杂度差异？

Question

我知道我们在递归和迭代算法之间确实存在空间复杂度差异。但是，我们之间也有时间复杂性差异吗？ 例如：如果我有一个递归计算列表中节点数的程序，然后我实现与迭代相同的程序，那么它的时间复杂度（即O（n））会有什么不同吗？谢谢

Answer 1

简答题：没有。

除非使用动态编程等优化算法，否则时间复杂度不会改变。也没有改变空间的复杂性，不知道你在哪里得到了这个想法..但是，在许多编程语言中，使用递归存在固有的开销，因为它们也必须存储堆栈，它使用更多的记忆。这可能会更慢，特别是如果它不是尾递归。