有刪除遞歸的模式嗎？

我有一個完美的算法，但它使用遞歸。我知道幾乎所有東西都有模式，但我無法找到這種情況。有刪除遞歸的模式嗎？

我只需要一些簡單的例子來說明如何修改算法，特別是方法或函數自己調用的部分。我已經看到了迭代算法，它在while循環中完成。所以必須有一個簡單的檢查清單，以便將遞歸算法轉換爲迭代算法。

您肯定可以使用迭代和自定義調用堆棧對遞歸進行建模。由於遞歸只不過是在新環境中執行相同的指令，所以可以使用簡單的堆棧結構爲自己的環境建模，然後將算法封裝在循環中，在迭代開始時推送當前的迷你環境並將其彈出每當完成循環迭代時，或通過break或continue過早退出。

2011-04-25 17:24:54 yan

正確，但確定什麼是「當前的微環境」並不總是微不足道的，特別是分支遞歸。 – Davy8 2011-04-25 17:34:10

順便說一句，如果您使用的是GCC或llvm，那麼打開-O2或-O3的非調試代碼將爲您執行尾遞歸消除。（如果你不知道，尾遞歸是當遞歸調用是函數中的最後一件事，並且簡單地被返回時，即不是表達式的一部分，參見http://en.wikipedia.org/wiki/Tail_call。）

因此，如果遞歸寫出更清晰的閱讀，最好堅持下去。

2011-04-25 17:34:29

只需添加，它不是簡單地說它是函數中的最後一個東西，但是當調用的返回值不用於創建當前的返回值時。即'return 4 + recur（i）;'不是尾遞歸的，因爲它的返回值仍然用於產生當前的返回值。 – yan 2011-04-25 17:38:41

謝謝你的提醒。 +1。編輯答案反映了這一點。 – 2011-04-25 17:59:28

遞歸發生在遞歸發生的尾隨遞歸，因爲函數的結束非常微不足道，使得循環無遞歸。有些編譯器甚至會自動爲你做。

以系統的方式將任何遞歸函數轉換爲迭代函數並不是那麼簡單，並且很可能最終創建自己的調用堆棧，這很可能會破壞實現非遞歸算法的目的。

2011-04-25 17:54:12 Davy8

回答