所有遞歸代碼都可以轉(zhuǎn)為非遞歸代碼

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

之所以所有的遞歸都能轉(zhuǎn)為迭代算法是因為遞歸借助函數(shù)調(diào)用，函數(shù)調(diào)用本身就是基于調(diào)用棧這種結(jié)構(gòu)實現(xiàn)的，只不過這一切都是自動完成的，我們當(dāng)然也可以用代碼手動模擬出來。

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

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

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

審核編輯 ：李倩