任何遞歸程序都能轉換為一個等價的非遞歸程序嗎？

簡單的遞歸轉非遞歸很容易，但是一些複雜的遞歸程序，比如遞歸下降的解釋器要改成非遞歸就非常困難了。

那任何遞歸程序都能轉換為一個等價的非遞歸程序嗎？

如果可以，可能構造出一個程序，自動地將遞歸程序轉換為等價的非遞歸程序嗎？

---

能 ，循環+棧。或者尾遞歸不需要棧。

反之亦然。

函數調用原理上都是語句的跳轉（GOTO）和壓入彈出棧而已。

---

部分程序可以不藉助棧轉換成等價非遞歸，請參考SICP第一章迭代相關內容，這太簡單，不展開說了

遞歸下降的解釋器就是去跑一棵樹而已，以二叉樹遍歷為例

def traversal(t):
if t is notNone:
traversal(t.left)
traversal(t.right)
dowith(t.element)


你試著把它用棧模擬一下（這可是基礎數據結構題，不會就看書）

然後你再想想怎麼棧模擬遞歸下降處理AST，開個腦洞，這也不難的

遞歸轉換成非遞歸，以尾遞歸為例，這貨名詞叫CPS，舉個簡單的例子感受一下，要學知識得自己去看書

基本原理是通過引入一個處理結果的函數，把遞歸變成尾遞歸，具體的你看代碼吧，非常簡單易懂了。。。

你說那個自動CPS變換程序，基本上就是自動構造上圖中的例子，這是函數式語言比較重要的一個東西了，因為遞歸是如此好寫又如此重要，所以基本現在的語言里都有自動CPS變換功能。

你之所以會問這些可不可以行不行的問題，就是因為沒學好基礎知識啊。。。

所以，抨擊基礎無用論的人，井裡的滋味好不好受我不知道，但是確實很多東西就看不到不知道了

---

可以。彙編沒有遞歸，機器碼也沒有遞歸，但高級語言有。

高級語言由低級語言實現。

所以，可以。

---

能

---

用這個鏈接自問自答一下

language agnostic

---

先改寫成嚴格的尾遞歸，然後套上while(true)

---

先前剛看了y組合子。。不知道是不是同一回事

---

推薦閱讀：