先說答案，這是肯定的，所有遞歸代碼都可以轉為非遞歸代碼。

之所以所有的遞歸都能轉為迭代算法是因為遞歸借助函數調用，函數調用本身就是基于調用棧這種結構實現的，只不過這一切都是自動完成的，我們當然也可以用代碼手動模擬出來。

我們知道將遞歸調用全部展開后其實會形成一棵樹，把遞歸轉為非遞歸無非就是在遍歷這棵樹，那么遍歷樹就有很多技術了，基于棧的深度優先遍歷Depth-first traversal，或者基于隊列的廣度優先遍歷breadth-first traversal都是可以的：

哦對了，說到算法，大家趕緊去關注小風哥的算法號，這個公眾號也是我親手寫的，只不過數據結構與算法這個話題有點宏大因此特意開了新號，大家快去關注吧。 說會遞歸轉為非遞歸這個話題，更理論一些的解釋是這樣的，不管是遞歸還是非遞歸，這兩者都是圖靈完備的，既然是圖靈完備，那么它們在表達能力上就是等價的，不存在誰不能轉為誰的問題。關于圖靈完備參考這篇《計算機科學中那些有趣的事實》。 只不過這存在一個難易程度的問題。 大家都知道尾遞歸最容易轉為非遞歸的迭代形式，本質上是這棵樹不是多叉的而是單叉的，單叉的不就退化成鏈表了嘛，遍歷鏈表當然是簡單的，但如果是多叉的話問題就沒那么簡單了，這里最有趣的是不存在一種模板可以讓我們直接用套路的形式把遞歸轉為非遞歸，因此這里存在一個問題：為什么你要把遞歸轉為非遞歸呢？因為最終你會發現將遞歸轉為非遞歸無非就是你自己接手了編譯器本來已經替你完成的工作，你會發現自己在手動模擬函數調用。

遞歸的優勢很明顯：代碼簡潔，容易理解和維護，其為人詬病的地方在于執行效率“可能”沒有非遞歸版本的高，但你最好理解這句話到底在說什么，到底哪里效率就不高了？ 我們知道函數調用本身并不是免費的，函數調用也是有代價的，這里的代價就在于維護函數調用以及函數返回需要額外執行一些指令，關于這部分的內容可以參考《函數調用時底層發生了什么？》，同時棧區空間有限，因此如果你的遞歸調用層級太多的話可能會導致棧溢出，撐爆你的運行時環境以及可能存在重復計算問題(可以利用memory table解決)，除此之外除非你有絕對令人信服的理由，否則你不應該試圖將遞歸轉為非遞歸。

審核編輯 ：李倩