是否有任何理由選擇迭代算法而不是遞歸算法

Question

我更喜歡用迭代算法實現遞歸方法。在學習考試時，我使用隊列實現了遞歸BFS（廣度優先搜索），但是在線搜索使用隊列的遞歸BFS時，我一直在閱讀，BFS是迭代算法而不是遞歸算法。那麼是否有理由選擇一個呢？

Answer 1

迭代和遞歸兩者都有相同的時間複雜度。差異是：遞歸程序需要更多的內存，因爲每次遞歸調用都會將程序狀態推入堆棧併發生堆棧溢出。但遞歸代碼易於編寫和管理。您可以減少通過使用tail recursion遞歸程序的空間複雜度。

Answer 2

迭代實現通常更快。斐波納契系列就是一個例子。在遞歸解決方案中通過簡單的循環實現它會更快。

更多的討論在這裏Recursion or Iteration?

Answer 3

迭代是計算機更高效。遞歸對程序員來說更高效，可能更優雅（可能）。

遞歸的問題是每次遞歸調用推動國家/幀到調用棧，可迅速導致資源深遞歸耗盡（堆棧溢出！）。但是，這些解決方案通常更易於編碼和閱讀。

迭代執行得更好，因爲它全部在本地框架中完成。然而，將遞歸轉換爲迭代可以降低由於引入變量以迎合算法進程而導致的可讀性。

選擇任何最容易編碼和維護的實現。只有擔心你是否有問題。