algorithm - 递归和迭代的运行时间

Question

我知道有一些算法对于递归和迭代策略都需要相同的运行时间。但我无法决定那个基础。

具有递归和迭代策略的算法是否可能总是需要相同的运行时间？

Answer 1

每个递归算法都可以简化为迭代算法（具有相同的运行时间）。 http://en.wikipedia.org/wiki/Recursion_(computer_science)#Recursion_versus_iteration

Answer 2

是的，如果一个算法可以优化为使用尾递归，那么它可以在没有额外代码的情况下转换为迭代，因此将具有相同的执行时间。

Answer 3

它可能具有相同的时间复杂度，但恒定的开销可能会有所不同（递归可能会更昂贵）。此外，如果使用迭代方法，递归会增加额外的空间复杂度。