遞歸與迭代

Question

我相信所有具有迭代邏輯的問題都可以使用迭代來解決，但是我們可以使用遞歸解決任何問題嗎？遞歸總是可以替代迭代嗎？如果可以的話，請提供您的答案的證明。還假設我們有一個無限的堆棧，或者我們在圖靈機上運行程序。我不在乎這個證明是否是一個理論證明。 （這就是我提到圖靈機的原因）

Answer 1

是的，遞歸總是可以代替迭代，這已經討論了before。從鏈接文章中引用：

因爲您可以使用嚴格迭代結構和僅使用遞歸結構的Turn完成語言來構建圖靈完全語言，因此這兩者因此是等效的。

解釋一下：我們知道任何可計算的問題都可以通過圖靈機來解決。並且可以構建一個編程語言A而不用遞歸，這相當於一個圖靈機。類似地，可以在沒有迭代的情況下構建編程語言B，其計算能力等於圖靈機。

因此，如果A和B都是Turing-complete，我們可以得出結論，對於任何迭代程序，都必須存在等價的遞歸程序，反之亦然。這是一個理論結果，因爲它不會給你任何關於如何從任意迭代程序導出一個遞歸程序的暗示，反之亦然。

Answer 2

是的。有一種稱爲tail recursion的遞歸類型，可以直接翻譯爲迭代。一個可以轉換成另一個沒有任何問題。因此，所有迭代解決方案都可以轉換爲遞歸解決方案。實際上，許多編譯器可以檢測到您正在執行尾遞歸，然後將其轉換爲for循環類型的代碼以提高效率。

Answer 3

當不需要循環時應使用遞歸，但在某種情況下該方法必須重複。例如，壓縮文件夾。如果有一個子文件夾，它應該自己調用（遞歸）。遞歸可以替代迭代，如果你想，但不建議。大多數人只是使用迭代，只在需要時才使用遞歸。