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

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

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

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

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

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

審核編輯 ：李倩