遞歸和迭代方法之間是否存在時間複雜度差異？

Question

我知道我們在遞歸和迭代算法之間確實存在空間複雜度差異。但是，我們之間也有時間複雜性差異嗎？ 例如：如果我有一個遞歸計算列表中節點數的程序，然後我實現與迭代相同的程序，那麼它的時間複雜度（即O（n））會有什麼不同嗎？謝謝

Answer 1

簡答題：沒有。

除非使用動態編程等優化算法，否則時間複雜度不會改變。也沒有改變空間的複雜性，不知道你在哪裏得到了這個想法..但是，在許多編程語言中，使用遞歸存在固有的開銷，因爲它們也必須存儲堆棧，它使用更多的記憶。這可能會更慢，特別是如果它不是尾遞歸。